kmjp's blog

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

TopCoder SRM 822 : Div1 Medium RedGreenBlueLight

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};
		}
		
	}
}

まとめ

ちょっと見当違いな方法とっちゃったな。