TopCoder SRM 825 : Div1 Medium SlowestNim

こちらはすんなり解けた。
https://community.topcoder.com/stat?c=problem_statement&pm=17429

問題

Nimで、両者最適手を取ると先手必敗となる山の状態が与えられる。
先手が、負けが確定するまでのターン数を最大化する場合、最大何ターンかかるか。
また、初手の1例を示せ。

解法

両者1ずつ石を取り除くことを強制できれば明らかに最大。
Nimの各山の石の数を2進数表記したとき、1が立っている位置が一番下の桁であるものを選ぼう。
そうすると、後手は1減らすことでしかGrundy数を0にできなくなる。

class SlowestNim {
	public:
	vector <int> move(vector <int> piles) {
		int N=piles.size();
		int sum=0;
		int i;
		int x=0,mi=30;
		FOR(i,N) {
			sum+=piles[i];
			int a=piles[i];
			int b=0;
			while(a%2==0) {
				a/=2;
				b++;
			}
			if(b<mi) mi=b, x=i;
		}
		return {sum,x,1};
	}
}

まとめ

解法もすぐ思いついたし、こちらはまぁよかったね。