AtCoder Regular Contest 143 C,E問題メモ

AtCoder Regular Contest 143

今回の難易度調整はなかなか綺麗な傾斜でよかったのではないでしょうか。（解けたとは言っていない）

C - Piles of Pebbles

• 石が積まれた山が $N$ 個あり、それぞれの山には $A_1,A_2,...,A_N$ 個の石がある
• 2人がゲームを行う
• ルール
  • 先手・後手交互におこなう
  • 各手番では、山を1個以上選び、選んだそれぞれの山から先手は $X$ 個、後手は $Y$ 個ずつ石を取り除く
  • 石の数が足りない山は操作対象として選ぶことはできない
  • 先に操作を行えなくなった方の負け
• 先手必勝か後手必勝か求めよ
• $1 \le N \le 2 \times 10^5$
• $1 \le X,Y,A_i \le 10^9$

Editorialを踏襲。

山を選んで石を取るゲームといえばGrundy数を使うNimが有名だが、これは2人の操作が同条件でないと使えない（はず）。
今回は先手と後手で取れる石の数が異なる。

ただ、考え方は似ていて、こういうゲームでは何らかの方法で「状態」を評価して、 「先手がいじった状態を、後手は必ず元に戻す方法があり、それを繰り返していくと先手が操作できなくなる」 みたいな法則がある場合が多い。

（もしくは、先手が先に操作することで、後手と先手を入れ替えて同様の展開に持ち込めるとか）

今回の場合、「同じ状態に戻せる」ような行動は何かと考えると、「先手が操作した山と同じ山を後手は選ぶと 各山の $\mod{X+Y}$ は変わらない」というのは比較的思いつきやすい。

この方針で考えを進めるとして、各 $A_i$ を $X+Y$ で割ったあまりの数列を考える。

先手が操作した山を、後手は必ず操作できる。
後手が先手と同じ山の組を選び続けることで、後手必勝。

$X \le Y$ か $X \gt Y$ かで場合分けが発生する。

先手を太郎、後手を次郎とする。

$X \le Y$ の場合、先手太郎は $X$ 以上の山を全て取るのがよい。すると、全ての山のあまりは $Y$ 未満となる。

その状態で次郎からゲームが始まったと考えると、 全ての山が $Y$ 未満の状況は先手である次郎から見ると①の状態となり、後手（＝入れ替える前の先手）である太郎が必勝。

$X \gt Y$ の場合、少し思考が深くなる。
あまりの数列の値は3種類ある。

• (1) $X$ 以上 $X+Y$ 未満
• (2) $Y$ 以上 $X$ 未満
• (3) $Y$ 未満

• (1) から $X$ 取ると、(3) になる
• (2) から $X$ 取ると、(1) か (2) になる
• (3) から $X$ 取ると、(1) か (2) になる

先手太郎の操作後、次郎からゲームが始まったと考えると、①または②a のいずれかの状態になる。

太郎としては自分が必勝の①の状態に持ち込みたい。
そのためには、次郎に渡す段階で、$Y$ 以上の山が1つもあってはいけない。

$Y$ 以上の山を1つでも残して渡してしまったら、②aの状態になり太郎は負ける。

(1)は全て選ぶことで $Y$ 未満にでき、(3)はもとから $Y$ 未満なので、(1)と(3)しかなければ①になり太郎（先手）必勝。

逆に (2) が1つでもあったら、取ろうと取るまいと $Y$ 以上となることを避けられず、②a の状態になるので、次郎（後手）必勝となる。

Python3

E - Reversi

• $N$ 頂点の木が与えられる
• 各マスにはリバーシの石が1つずつ置かれており、白黒どちらの面が表になっているかも与えられる
• 以下の操作を繰り返す
  • 白が表になっている石を1つ選び、取り除く
  • その後、石が置かれていた頂点に隣接する、まだ石が置かれている頂点について、その石を全て裏返す
• 上手く操作順を決めることで全ての石を取り除くことが可能か判定せよ
• 可能な場合は、取り除く石の頂点番号を順に並べた数列のうち、辞書順最小のものを求めよ
• $1 \le N \le 2 \times 10^5$

葉から決める。

葉の頂点は、隣接頂点が1つだけ。
葉の頂点を $u$、その唯一の隣接頂点を $v$ として、 この2つのどちらを先に操作しなければならないかは、$u$ の色によって一意に決まる。

• ① $u$ が白の時、$v$ を先に操作して $u$ が黒になってしまったら、もう $u$ を白にする手段はなく、破綻する
  • →$u$ を先に操作しなければならない
  • この時、$v$ は自身の操作前に1回、ひっくり返される
    • もし複数の白の葉に隣接していたら、その都度ひっくり返される
• ② $u$ が黒の時、$v$ を先に操作するまで $u$ は取れない。$v$ が操作されたらいつでも取れる
  • →$v$ を先に操作しなければならない

①        ②
  ：        ：
v ◎        ◎先
  ｜        ｜
u ○先      ●

すると、次は $u$ を取り除いたグラフ上で同じ問題が解ければよくなる。
①の場合は $v$ をひっくり返した状態を、新しいグラフ上での初期状態とする。

葉を取り除くことで新たに葉となる頂点が生まれたりして、これはグラフが1頂点になるまで繰り返せる。

最終的に残った1頂点が黒となってしまったら不可能。
白だったら可能となる。

辞書順最小の操作順を考える。

前述の操作によって、各辺につき「$a$ は $b$ より先に操作しなければならない」という条件が1個ずつ、計 $N-1$ 個できている。
この条件を全て満たせば、必ず全ての石を取り除ける。

トポロジカルソートを行えばよい。
「自身より先に操作しなければならない頂点がない頂点」は、初手から自由に選べる。 これを最初の候補として、この中から1個ずつ選び操作を確定させていき、順次「自身より先に操作しなければならない未操作の頂点がなくなった頂点」を候補に加えていけば、適切な操作順を構築できる。

そのとき、候補が複数あったらheapqを使って小さい順に取り出すことで、辞書順最小を達成できる。

葉から1個ずつ切り取っていくという解法はたまに見るが、これもそれで行けることになかなか気づけなかった。

Python3