kmjp's blog

競技プログラミング参加記です

TopCoder SRM 664 Div2 Medium BearPlaysDiv2

こちらは割とオーソドックス。
http://community.topcoder.com/stat?c=problem_statement&pm=13939

問題

石の山が3つあり、初期状態でそれぞれA,B,C個の石からなる。
このうち2つの山を選び、小さい方の山の石の数が倍になるよう、大きい方から石を移す、という処理を任意回数行える。
最終的に3つの山のサイズを同じにできるか判定せよ。

解法

3つの山の石の数の合計は変わらないので、2つ分の山の状態だけ保持して探索していけば良い。
A,B,Cの上限N=500とすると、状態の数はO(N^2)。
そこからの遷移の仕方は山の選び方3通りだけなので結局O(N^2)の時間で済む。

int dp[1000][1000];

class BearPlaysDiv2 {
	public:
	string equalPiles(int A, int B, int C) {
		if(A>B) swap(A,B);
		if(B>C) swap(B,C);
		if(A>B) swap(A,B);
		
		int T=A+B+C,i;
		if(T%3) return "impossible";
		ZERO(dp);
		dp[A][B]=1;
		queue<pair<int,int> > Q;
		Q.push({A,B});
		while(Q.size()) {
			auto r=Q.front();
			Q.pop();
			int a=r.first,b=r.second,c=T-a-b;
			if(a==b && b==c) return "possible";
			
			int vec[3][3]= {
				{a*2,b-a,c},
				{a*2,c-a,b},
				{b*2,c-b,a},
			};
			FOR(i,3) {
				sort(vec[i],vec[i]+3);
				if(dp[vec[i][0]][vec[i][1]]==0) dp[vec[i][0]][vec[i][1]]=1, Q.push({vec[i][0],vec[i][1]});
			}
		}
		return "impossible";
	}
};

まとめ

A,B,Cの数3つで状態を取るとメモリも時間も間に合わない。
A+B+Cが固定なので、実質2つ覚えておけばいいことに気づけばあとは簡単。