kmjp's blog

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

TopCoder SRM 737 Div1 Easy AliceAndBobEasy

Easyは割とすんなり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=15076

問題

N個の山があるNimの初期状態のうち、先手が勝利のために取れる第1手のパターンが最多の物を構築せよ。
ただし、初期状態では各山の石の数は異なっていなければならない。

解法

初期状態の石の数の列をAとし、全要素のxorを取った値をXとする。
先手がi番目の山をy個残すように石を取る場合、X^(A[i])^yが0になるように石を取ればいいので、X^(A[i])≦A[i]であればそのような石の取り方ができる。

Aの要素数が奇数のとき、A[i]の最上位ビットをすべてそろえておけば、X^A[i]の最上位ビットはA[i]の最上位ビットより下の位置にあるため、どの山から石をとってもそのような取り方が可能である。

偶数のときは、1個だけ最上位ビットが低いものを作っておこう。
それ以外の山であれば、条件を満たす石の取り方ができる。

class AliceAndBobEasy {
	public:
	vector <int> make(int N) {
		vector<int> V;
		int i;
		if(N%2==1) {
			for(i=1;i<=N;i++) V.push_back((1<<20)+i);
		}
		else {
			for(i=1;i<=N-1;i++) V.push_back((1<<20)+i);
			V.push_back(1);
		}
		return V;
	}
}

まとめ

問題名に反し、Div2MediumよりDiv1Easyの方が難しい。