TopCoder SRM 651 Div1 Medium FoxConnection3

本番はこの解に至れなかった。

問題

２次元の無限に広がるグリッドがある。
初期状態でN匹のキツネがおり、それぞれの位置が与えられる。

各キツネを移動し、それぞれのいるセルが隣接マスを辿って連結するようにしたい。
各キツネの総移動回数を最小化せよ。

解法

まずDFSなどで総当たりし、N個の連結マス群が成す形状を求める。
N=6でも216通りなのでさほど時間がかからない。

各形状に対し、どのキツネが連結マス群中どのマスに対応するかをN!通り試す。
連結マス群の形状と、キツネの対応を決めたら連結マス群の位置を決める。

連結マス群の位置はX座標方向およびY座標方向それぞれで総移動回数が最小値となる場所を求めればよい。
連結マス群の位置に対応する総移動回数は、X座標方向・Y座標方向それぞれに対し下に凸なので、三分探索で求められる。

class FoxConnection3 {
	public:
	int N;
	set<set<pair<int,int> > > S[9];
	
	ll tot(vector<ll>& V,ll dif) {
		ll tot=0;
		ITR(it,V) tot+=abs(*it+dif);
		return tot;
	}
	
	ll mini(vector<ll>& V) {
		int i;
		ll L=-1LL<<30,R=1LL<<30;
		ll mi=1LL<<50;
		while(R-L>=4) {
			ll m1=(L*2+R)/3;
			ll m2=(L+R*2)/3;
			ll v1=tot(V,m1);
			ll v2=tot(V,m2);
			if(v1==v2) L=m1,R=m2;
			if(v1<v2) R=m2;
			if(v1>v2) L=m1;
		}
		for(ll a=L;a<=R;a++) mi=min(mi,tot(V,a));
		return mi;
	}
	
	long long minimalSteps(vector <int> X, vector <int> Y) {
		int N=X.size();
		ll mi=1LL<<60;
		int i,j;
		
		set<pair<int,int> > ts;
		ts.insert(make_pair(0,0));
		S[1].insert(ts);
		
		for(i=1;i<=X.size()-1;i++) {
			ITR(it,S[i]) {
				set<pair<int,int> > s=*it;
				
				ITR(it2,s) {
					int cx=it2->first,cy=it2->second;
					FOR(j,4) {
						int dd[4]={1,0,-1,0};
						int tx=cx+dd[j],ty=cy+dd[j^1];
						if(s.count(make_pair(tx,ty))) continue;
						set<pair<int,int> > s2;
						int dx=(tx<0),dy=(ty<0);
						s2.insert(make_pair(tx+dx,ty+dy));
						ITR(it3,s) s2.insert(make_pair(it3->first+dx,it3->second+dy));
						S[i+1].insert(s2);
					}
				}
				
			}
		}
	
		ITR(it,S[X.size()]) {
			vector<int> V;
			set<pair<int,int> > CS=*it;
			vector<pair<int,int> > C;
			ITR(it2,CS) C.push_back(*it2);
			
			vector<ll> xs(N,0),ys(N,0);
			FOR(i,N) V.push_back(i);
			do {
				
				FOR(i,N) xs[i]=C[V[i]].first-X[i];
				FOR(i,N) ys[i]=C[V[i]].second-Y[i];
				mi=min(mi,mini(xs)+mini(ys));
			} while(next_permutation(V.begin(),V.end()));
		}
		
		return mi;
	}
}

まとめ

最初１匹は位置を固定すると考えてしまい、サンプルが通らなかった。
T字状に３匹いる場合など、全員動かないといけないパターンもあるのね。