C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder豆一つをnimの山として考えられる。 よって、全ての茶碗についてgrundy数を求め、A[i]回xorを取った物たちをxorすればいい。難しいのはgrundy数を求める方法。 区間 [ i - c[i] , i ) に含まれない最小…

A - Taro vs. Jiro解法 Kの制約が大きすぎるので、少ない場合と同じに考えられることが予想できる。 実際に考えてみると、Kが1なら隣にBがあれば勝ち。 次にどんな操作をされても、Bに戻せるため、Kが奇数のときと1の時を同視していいと分かる。 Kが偶数の場…

B - 石取り大作戦 問題概略 石がN個あり、先手は1~A個、後手は1~B個取れる。 最後の石を取ったほうが勝ちの場合、最適でどちらが勝つか。解法 A >=N の時は明らかに先手が勝つ。 それ以外の場合を考える。A==Bの時を考える。 N %(A+1)!=0 の時Aが勝ち、それ…

E - Prefix-free Game 問題概略 0,1の高さLの完全二分木でお互いにコマを置いていく。コマが置かれた親と子は使えない。置けなくなったら負け Sn で初期配置が渡される 制約 1≤N≤1051≤N≤105 1≤L≤10181≤L≤1018 s1s1, s2s2, ..., sNsN はすべて相異なる。 {s1,…

D - An Ordinary Game 問題概略 長さ3以上の文字列sが与えられる。二人でゲームを行う。 sから両端以外の文字を一つ取り除く。ただし、その結果同じ文字が隣り合ってはいけない。 先に操作を行えなくなったほうが負け。 制約 3≤|s|≤1053≤|s|≤105 ss は英小文…