TopCoder SRM 619 Div1 Easy SplitStoneGame

SRM619に参加。600ptのMediumを通せたおかげで前回落としたレートが回復。
http://community.topcoder.com/stat?c=problem_statement&pm=13113

問題

N要素の正の整数からなる数列が与えられる。
2人で交互に以下の手順を行う。

• 数列中正の整数が入っている箇所を選ぶ。
• その数値を正の整数2つに分割し、他の正の整数が入っている要素2か所にそれぞれ足しこむ。元々選んだ場所の値は0になる。
• 上記の選び方ができない場合は負け。

解法

上記条件より、

• 2つに分割するには2以上の要素が1個はないとその時点で負け
• 分割した整数を他の2か所の要素に足しこむので、上記要素以外に1以上の要素が2個はないと負け

初手を除くと、数値の加算により最低1か所は2以上の要素ができるので、「2以上の要素がない」は初手だけ考えればよい。
後の処理は、1回処理するごとに正の整数要素が1個減る。要素数が2個以下だと負けなので、結果として要素数が偶数だと負け、奇数だと勝ち。

DPで解いてもN<=50で[1の要素数][2以上の要素数]で状態を持てばO(N^3)で解ける。

class SplitStoneGame {
	public:
	string winOrLose(vector <int> number) {
		int N=number.size();
		sort(number.begin(),number.end());
		if(number[N-1]==1) return "LOSE";
		if(N<3) return "LOSE";
		if(N%2) return "WIN";
		return "LOSE";
		
	}
}

まとめ

苦手な二人相互ゲームだったが、今回はすんなり解けてよかった。