yukicoder No.524 コインゲーム

問題

https://yukicoder.me/problems/no/524/

制約

0 \lt N \lt 2^{32}

考え方

Nimであるから (1 \le i \le N) なる i とのXORをとって 0 かどうか判定すれば良い。ナイーブに計算するとO(N) で間に合わない。

各ビットごとに計算して、それぞれ 0 であれば負け。そうでなければ勝ち。と考えることにする。そのとき [1, N] までの k ビット目に含まれる 1 の数は

\displaystyle \lfloor \frac{N}{2^k} \rfloor \times 2^{k-1} + N - 2^k \times \lfloor \frac{N}{2^k} \rfloor - 2^{k-1} + 1

である。 N までに含まれる各ビットは周期性があることからわかる。

よってそれぞれの k ビット目について偶奇を判定すればよい。1 つでも奇数があれば O 。すべて偶数であれば X となる。

#307092 No.524 コインゲーム - yukicoder

どこに着目して考察するべきだったか

Nim であること。XORの周期性。

何がバグっていたか

得た知見

類題