ABC004 D - マーブル

D - マーブル

概要

数直線上の整数点に箱がある。
赤玉がR個、緑玉がG個、青玉がB個あり、それぞれ数直線上の地点-100、0、100の箱に入っている。
この玉を1つずつ隣に移動させ、各地点にある箱にある玉の数が多くとも1つにしたい。ただし、玉を移動する際は異なる色の玉が同じ箱に入らないように移動させる。
玉を移動するための最小手数を求めよ。

制約

1 <= R, G, B <= 300

共通方針

各玉の移動回数はabs(その玉の最終的な場所 - その玉の元々の箱の場所)で求まる。
最適な置き方では、同じ色の玉は隣接している。ただし、異なる色の玉同士が隣接していない場合もあるため注意。

方針①

緑玉の置き場所を先に決めると、その置き場所に従い赤玉と青玉の最適な置き場所が定まる。
なので、すべての緑玉の置き方を試す。

緑玉の置き方を決めた後の赤玉の置き方について。
自分の箱を中心に左右に広がるような置き方が最も移動回数が少ないため、赤玉がそのように置けるならそのように置く（緑玉が十分右に置かれている状態）。そのようにおけない場合（緑玉が左に来ている状態）は、緑玉の左に隣接して赤玉があるように置く。

青玉の置き方も同様。

感想①

各玉の境界がちょっとなおざりですが、一応通りました。

解答①

Submission #4148117 - AtCoder Beginner Contest 004

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
ll val(ll x){
	if(x % 2 == 0) return (x / 2) * (x / 2);
	return ((x - 1) / 2) * ((x - 1) / 2 + 1);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll R, G, B;
	cin >> R >> G >> B;
 
	ll ans = 1e10;
	for(ll g = -300; g <= 300; g++){
		ll t = 0;
 
		for(ll i = g; i < g + G; i++){
			t += abs(i);
		}
 
		if(R/2 - 100 < g){
			t += val(R);
		}else{
			for(ll i = g - R; i < g; i++){
				t += abs(i + 100);
			}
		}
 
		if(100 - B/2 >= g + G){
			t += val(B);
		}else{
			for(ll i = g + G; i < g + G + B; i++){
				t += abs(i - 100);
			}
		}
 
		ans = min(ans, t);
	}
 
	cout << ans << endl;
}

方針②

dp[i][j] ：iの位置にいるときに残り玉数がjの場合の最小手数　としてDPする。DP式は下記の通り。
dp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j))

cost(i, j)

iの位置にいるときに残り玉数がjのとき、次の玉を置くときに発生する移動手数。
左から置いていこうとすると赤→緑→青の順に置かれるので、残りの玉数だけで玉の色が把握可能。

DPの遷移

dpのi= 0は地点-500を意味する。

どの位置にいても玉を置いていなければ手数0。(dp[i][total] = 0)
赤玉が置かれる可能性がある最も左端の地点(i=0, 地点-500)からスタートする。
(i=1, 地点-499)だと、dp[1][total-1]が更新され、dp[1][total-2]以降は更新されない。
(i=2, 地点-498)だと、dp[2][total-1], dp[2][total-2]が更新され、dp[i][total-3]以降は更新されない。
ちょっとずつ置かれる玉が増えていくイメージ。
玉をどんどん置いていくと玉の色が変わるが、それはcost(i, j)で勝手に計算してくれる。

感想②

下記を参考にしました。
submissionもほぼそのままです。
competitive-kivantium.hateblo.jp

解答②

Submission #4148226 - AtCoder Beginner Contest 004 | AtCoder

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int R, G, B;
int dp[1000][1000]; // dp[pos][remain] = number of move
 
int cost(int pos, int remain) {
    if(remain >= G+B) return abs(400-pos);
    else if(remain >= B) return abs(500-pos);
    else return abs(600-pos);
}
 
int main(void) {
    cin >> R >> G >> B;
    int total = R + G + B;
    REP(i, 1000) REP(j, 1000) dp[i][j] = 1e9;
    REP(i, 1000) dp[i][total] = 0;
    FOR(i, 1, 1000) {
        REP(j, total) {
			// cout << i << " " << j << " " << dp[i-1][j] << " " << dp[i-1][j+1] << " " << cost(i, j) << endl;
            dp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j));
        }
    }
    int ans = 1e9;
    REP(i, 1000) {
        ans = min(ans, dp[i][0]);
    }
    cout << ans << endl;
}

その他感想

ネットワークフローでも解けるらしい。