メモ

yukicoderでゆるふわgolf

yukicoder No.524 コインゲーム

問題はこち
No.524 コインゲーム - yukicoder

Nimなので問題は「1~Nまでxorをとったものが0か否か判定せよ」と読み替えられる。(このことの証明は以前した:yukicoder No.2 素因数ゲーム - メモ
以下では「1~Nまでのxorをとったもの」をxor和と呼ぶことにする
・最下位bitについて
xor和の最下位bitをN=1のときから順に並べると1,1,0,0,…という長さ4の周期性を持つことがわかる
(次にxorするのが0or1、今の値が0or1、の4通りの状態しかないことから明らか)
よって xor和の最下位bitが0⇔N≡3,0 mod 4
・それ以上の位について
xor和の最下位bitを除いたものをN=1のときから順に並べると 0、非0、0、非0…という長さ2の周期性を持つことがわかる
これは偶数kに対し、kとk+1は最下位bitを除いて等しいことと、同じ値同士のxorは0になることからわかる
よって xor和の最下位bit以外が0⇔Nが奇数

この2つをあわせて、xor和が0⇔N≡3 mod 4がわかる

n;main(){putchar(~atoi(gets(&n))%4?79:88);}

43B
nをmainの引数とするとセグフォ