こちらは割とオーソドックス。
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つ覚えておけばいいことに気づけばあとは簡単。