Editorial賢いなぁ。
https://community.topcoder.com/stat?c=problem_statement&pm=17372
問題
整数列Sに対し、以下のゲームを行う。
先手は、各要素に3色のいずれかを割り振る。
後手は、3色のうち1色を指定し、その他2色を割り振られた要素を消す。
残された要素はデクリメントする。
この際、S中で0に到達した要素があれば先手が勝ち。Sが空なら後手の勝ち。
Sに正の整数が残っているなら上記処理を繰り返す。
Sが与えられたとき、先手必勝か、必勝なら初手を答えよ。
解法
Sの各要素sに対し、(1/3)^sの値を対応付けたたとする。
合計が1以上であり、3色に塗り分けた際にいずれも各要素に対応付けた値の合計が1/3以上なら先手必勝である。
こうすると、後手の作業は合計値が最小のものを残すことに相当するし、デクリメントは値を3倍することに相当する。
ということで、(1/3)^sの和が1/3を3つ以上作れるか判定していけばよい。
class RedGreenBlueLight { public: vector <int> move(vector <int> steps) { int N=steps.size(); vector<vector<int>> V[1020]; int i,j; FOR(i,N) if(steps[i]<=1010) V[steps[i]].push_back({i}); for(i=1010;i>=2;i--) { while(V[i].size()>=3) { vector<int> W; FOR(j,3) { FORR(a,V[i].back()) W.push_back(a); V[i].pop_back(); } V[i-1].push_back(W); } } if(V[1].size()>=3) { vector<int> R(N); FOR(i,3) FORR(a,V[1][i]) R[a]=i; return R; } else { return {-1}; } } }
まとめ
ちょっと見当違いな方法とっちゃったな。