Codeforces Round 557 (Forethought Future Cup – Final Round)

A. Hide and Seek

隣接対が $O(N)$ 通りしかないのですべて判定すればよいです．判定は各地点に対して最初・最後に $x$ に現れる場所を求めておけばできます．

周期があればその倍数も周期なので，$N/p$ の形の約数について周期になっているかどうかをチェックすればよいです．

最初に $0$ 個の山を作る手を打ったプレイヤが負けです．相手はその次のターンで，前回選ばれなかった山をすべて空にします．

すると，$1$ 個の山が $n/2+1$ 個以上ある状態で手番を迎えたプレイヤが負けです．すると，最初に $1$ 個の山を作る手を打ったプレイヤが負けることが同様に分かります．

これを繰り返して，勝利条件は $\min(a)$ の個数で記述できることが分かります．

短い方の桁数 $m$ を固定した上で線形時間で解ければよいです．

「$n+m$ 個の 0/1 を決める」「この 2 点の値は同じ / 反対」という制約が与えられているだけです．制約をグラフの辺と見なすと，連結成分上では値は高々 $2$ 通りに決まります．

質問を辺としてグラフを作ると連結成分が複数できるとダメです．そこでとりあえず $2$ 回の質問で全体がパスになるように質問します．等号であると分かった部分をまとめると，「隣接するコインは異色である」という情報が分かった状態になります．

この状態から，$(i,i+2)$ という質問をすべて行えば，左から順に決まっていきます．この種の質問をするのに $2$ 回かかり，合計 $4$ 回の質問で解決しています．

すごい．

必ず Bob 勝ちで，適当な完全マッチングをとってそれに沿ってプレイすることで勝利可能です．そのようなマッチングがあるとして成り立っていて欲しい条件を考えると，単に安定マッチングをとればよいことが分かります．

仮に Alice が左側頂点からスタートで，Bob は前回よりも大きい辺，Alice は前回よりも小さい辺を選ぶゲームだとします．あるマッチングに沿ったプレイが破綻するのはどのような場合かというと，

となっている場合です．この $a_2b_1$ はどういう辺かというと

となっている辺です．「Alice は重みが大きいものを好む」「Bob は重みが小さいものを好む」とした安定マッチングをとると，このような辺は存在しません．