Codeforces Round 1047

A. Collatz Conjecture

$2^kx$ が条件を満たします．

$p_i+q_i=N+1$ となるようにすれば条件を満たします．

even の条件を無視すれば，$k=1$ または $k=b$ を調べることになります．

この場合に近くてこの場合と偶奇が変わりうる，$k=1,2,b/2,b$ を候補として調べます．

$b_i$ では各 $k$ の個数が $k$ の倍数になってることが必要で，その場合の構築も簡単です．

初期状態での mex を $X$ とします．

$1$ 回の操作後では，

– 頻度 $2$ 以上だったものは $X$ に変化する．

– 頻度 $1$ だったものは $X$ とそれの $\min$ に変化する．

ため，最大値以外の頻度が $1$ 以下になります．よって，初期状態が「最大値以外の頻度が $1$ 以下」を満たすとしてよいです．

この状態での mex を改めて $X$ とします．$0,1,\ldots,X-1$ の頻度が $1$ であることから，それらは操作で不変になります．$X$ の個数が $1$, $2$ 以上で場合分けして，ここから先は周期 $2$ のパターンになることが分かります．

各 $i$ に対して，$i$ が good になるような $[l,r]$ を数えるという方針にします．

$a_i=b_i$ ならば，$i\in [l,r]$ となる $[l,r]$ すべてが条件を満たします．

そうでないとき，$[l,i)$ に $a_i$ 以上の要素が必要です．$[l,i)$ に $b_i$ 以上の要素が必要です．

これらが十分条件になっていることも分かります．

適当な方法で「時刻」を定義します．時刻が増えるにつれて，赤頂点の個数が増えて，単調に River が勝ちやすくなります．

よって，次の値が定義できます．

– $\mathrm{dp}[v][player]$: 頂点 $v$ でプレイヤー $player$ 手番という状態からゲームを開始したときに，River 勝利になるような最小時刻．

これを topological 逆順に求めていけばよいです．