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の方が難しい。