ferinの競プロ帳

競プロについてのメモ

summerFestivalContest EEEEndless gamEEEE

問題ページ
Hamako Online Judge

考えたこと

ゲーム系の問題でN個の石の山と言われればまあgrundy数を思い浮かべる。
0個の状態のgrundy数を0としてgrundy数を求められれば解けそう。

神通力についてはXORを取った結果が0なら何もしない、XORを取った結果と等しいgrundy数の山があればその山を複製すれば0となるのでMMNMMさんが勝てる。そんなに難しい処理は必要なさそう。

各NについてのPはエラトステネスの篩で前計算しておけば計算量的に問題ない。

とりあえずgrundy数を愚直に求めてみる。
遷移先のgrundy数を管理するのをunordered_setからsetにしたら速度が目に見えて上がった。
これくらいの要素数ならsetのほうが早そう?
再帰関数で書いたらスタックオーバーフローしたっぽかったのでforで書き直す。
出したら部分点が来た。

これ以上の高速化は思い浮かばなかったので解説を読む。
seg[i] = (grundy数がiの最大の石の数の山) とする。
N個の石の山のgrundy数がxであるかの判定をする。seg[i](0<=i<=x)の最小値がN-min(p, k)以上であれば遷移先に0からxのgrundy数の石の山が全て存在すると言える。つまり、N個の石の山のgrundy数はxより大きいといえる。xについては単調性があるので二分探索をすればxをlogオーダーでできそう。seg[i]の最小値を求めるのはRMQのセグメントツリーを使えばこれもlogオーダーでできる。
よって、O(max(A)*log^2K)でgrundy数を求めることができる。

学び

連続している区間のmexを求めるときはセグ木+にぶたんで求められる。