AtCoder Regular Contest 105 C,D,E問題メモ

AtCoder Regular Contest 105

ゲーム問題が2問。解きたかったけどEはむずかった。

C - Camels and Bridge

• ラクダ $N$ 匹が隊列を組んで橋を渡る
• $i$ 番目のラクダの体重は $w_i$
• 橋は $M$ 個の区間に分けられ、$i$ 番目の区間の長さは $l_i$、耐荷重は $v_i$
• 橋の渡り方は以下のようにする
  • ラクダを好きな順に、好きな間隔を空けて一列に並べる
  • ラクダたちはこの距離を保ったまま移動する
  • $i$ 番目の区間を通っているラクダの体重合計が $v_i$ より大きくなると橋は崩落する
• 橋を渡りきれる隊列の長さの最小値を求めよ
  • 渡りきるのが不可能な場合は-1を答えよ
• $2 \le N \le 8$
• $1 \le M \le 10^5$
• $1 \le l_i,v_i,w_i \le 10^8$

見て！ラクダが橋を渡っているよ！かわいいね
                4     8      3
               🐫   🐫    🐫 )))
  |-----10------|--8--|---20---|

ラクダの合計体重が橋の耐荷重を超えたので、橋は崩落してしまいました
お前のせいです
あ～あ
                  3
                 🐫
  |____💀__💀__|--8--|---20---|

$N$ が小さいので隊列の順番を総当たりするのは予想が付くが、1つの隊列を固定したときの最小値の求め方は多少工夫の必要がある。

$8!=40320$ なので、この全てで $O(M)$ かかる計算（橋の区間1つ1つを調べるなど）をしていては、間に合わない。

まず不可能判定をする。ラクダ間の距離をめっちゃ離せば橋の上に同時に1匹のラクダしか乗っていないようにできる。 それで無理というなら、1匹のみの体重で耐荷重を超えてしまうということ。つまり、最小の $v_i$ が最大の $w_i$ 未満ならアウト。

以下、渡りきることは可能とする。

ラクダの合計体重が $V$ を超えたら、距離は $L$ 以上離さなければならない、という関係性を作る。

例えば橋の区間の長さと耐荷重は以下だったとして、

l       13         5       8
v |-----10------|--8--|---20---|

$v$ の昇順にソートすると、まず重さ8を越えたら距離5離さないといけないと分かる。
次、重さ10を越えたら距離13離さないといけない。
最後は重さ20と距離8だが、これは既に重さ10の時点でそれ以上離れてないといけないので、意味の無い制約となる。

最終的に、関係性の配列はこんな感じになる。（便宜的に0を補う）

L [0,  5,  13]
V [0,  8,  10]

次に、ある並び順を固定したラクダ達を考える。

1つの区間の上に同時に乗りうるラクダは、隊列の中で連続している。左端のラクダを $c_l$、右端を $c_r$ とすると、その間の合計体重が分かる。

これが同時に橋の上に乗った時に離さないといけない距離は、$V$ を二分探索して、そのindexを $L$ から参照すれば分かる。
具体的にどのようにバラせばよいかはともかく、$c_l$ と $c_r$ は、その距離だけ離さなければならない（そして離せば隊列の当該部分に関しては大丈夫）ことは確実。

これを、$\dfrac{N(N-1)}{2}$ 通りの全てのペアについて求めると、全てのペアで最低限離さなければいけない距離が分かる。 これを統合すると、全体の距離が求められる。

計算量は、関係性の配列に $O(M \log{M})$、最小距離を求めるのに $O(N!N^2 \log{M})$ となる。

Python3

D - Let's Play Nim

• 2人で変則Nim（石取りゲーム）をする
• $N$ 個の袋と $N$ 枚の皿がある
• はじめ、袋にはそれぞれ $a_i$ 個のコインが入っており、皿には何も乗っていない
• 先手と後手が順に以下のいずれかを行う
  • コインの入った袋が1つ以上存在するとき、その中から好きな袋を1つ選び、中身を好きな皿に全て移す
  • コインの入った袋が存在しないとき＜、コインがのった皿を1つ選び、1枚以上のコインを取り除く
• 先に行動できなくなった人の負け
• 上手く行動したとき、先手必勝か後手必勝か判定せよ
• $1 \le N \le 10^5$
• $1 \le a_i \le 10^9$

気付けば単純なので、ちゃんと証明してなくても多分こうだろでも通せちゃう。

Nimを知っていることがある程度前提となる。
Nimは、この問題における「コインの入った袋が存在しないとき」の部分のゲームであり、初期配置の各皿のコインの数の総xorが0なら後手必勝、それ以外なら先手必勝となる。

袋から皿に移していくフェイズ（前半フェイズ）は $N$ 回あり、奇数の場合は全体の先手後手とNim部分の先手後手が入れ替わる。

さて、前半フェイズの最終手の人は、Nimでは後手となるので、何としても各皿のコインの総xorを0にしたい。

逆に、もう一方は最終手直前でどこに置いてもそれが不可能な状態で渡したい。

普通、総xorを0にするのってそう簡単じゃない。
唯一、$(2,2,7,7,10,10,...)$ みたいに同じコインの袋が同数だけあったら、真似っこしていけば常に0を保てるので、Nimの後手必勝となる。

しかし、それ以外の場合は不可能で、Nimの先手必勝となる。

証明は、「全コインの過半数が乗った皿」を作れることからできるようだ。なるほど。

一般に、$A \ xor \ B = A+B - 2(A \& B)$ → $A \ xor \ B \le A+B$ なので、 $X$ が過半数なら $X \gt A+B+C+... \ge A \ xor B \ xor ...$ なので、$X$ 以外の数のXORで $X$ を作りたくても無理。

Python3

E - Keep Graph Disconnected

• $N$ 頂点 $M$ 辺の単純無向グラフが与えられ、辺 $i$ は頂点 $(a_i,b_i)$ を結ぶ
• はじめ、頂点 $1$ と $N$ は非連結
• 先手と後手が、交互に次の操作を行うゲームをする
  • 「単純」かつ「頂点 $1$ と頂点 $N$ が非連結」な状態を保ったまま、グラフに1本ずつ辺を追加する
• 自分の手番で追加できなくなった人の負け
• どちらが勝つか求めよ
• $2 \le N \le 10^5$
• $0 \le M \le 10^5$

頂点 $1$ を含む連結成分の頂点数を $S$、頂点 $N$ を含む連結成分の頂点数を $T$ とする。

最終状態は、頂点 $1$ を含む完全グラフと頂点 $N$ を含む完全グラフの2つだけが存在している。

その時の総辺数は $\dfrac{S(S-1)}{2}+\dfrac{T(T-1)}{2}$ となるので、 最初からある $M$ 本を引くと「あと何本辺が追加できるか」つまり「先手勝ちか後手勝ちか」がわかる。

追加できる本数が、先手は奇数に、後手は偶数になるように、$S,T$ を持っていきたい。

だが、$\dfrac{S(S-1)}{2}$ の偶奇は $S$ を4で割ったあまりで変化し、$T$ 側も4周期、 さらに $M$ の偶奇でも先手後手の目指すものが異なり……とこんがらがってくる。

まずは $T=N-S$ とすると、「$N$ が奇数の場合」という大きな区分で答えを求めることが出来る。

代入すると $S(S-N)+\dfrac{N(N-1)}{2}$ となり、$S(S-N)$ は $N$ 奇数の時は必ず偶数となる。
よって $S$ によらず $N$ だけで偶奇がわかる。

「必ず奇数」とか「必ず偶数」でなくて、 「$N$ の値によって偶数にも奇数にもなるけど、$N$ だけに依存する」で切り取るの、気付きそうで気付かない。

考慮すべき状態が半分に減った。

$N$ が偶数の時は、$(S,T)=(偶,偶) or (奇,奇)$ で最終状態の辺数の偶奇が異なるため、先手と後手が頭を使う余地が残る。

※この2通りの場合分けでよいのは、先ほどの $S(S-N)+\dfrac{N(N-1)}{2}$ を使えば、 $S(S-N)$ の偶奇が（$N$ は偶数とわかっているので）$S$ の偶奇のみによって切り替わることから言える。

先手、後手は、$N,M$ の値から、$(S,T)$ を $(偶,偶)$ に持っていきたいか $(奇,奇)$ に持っていきたいか決まる。 （実際にどちらかで試してみて、先手は追加できる辺数が奇数ならそのまま、偶数なら逆を目指す）

取りうる手を考える。初期状態で $S$ にも $T$ にも属さない連結成分を「浮いている」成分と呼ぶと、

• 浮いている成分を $S$ や $T$ にくっつける
• 浮いている成分同士をくっつける
• 連結成分内の頂点同士を結ぶ

と様々で、特に最後の手は「今の状態で全ての成分が完全グラフとなったら不可能」など、条件の管理が非常に難しい。

だが「初期～途中状態での $S,T$ の偶奇」と「頂点数が奇数の浮いている成分」に着目し、 これを変化させる手を考えると、複雑な条件は考えずともよくなる。

以下、「頂点数が奇数/偶数の浮いている成分」を「奇数成分」「偶数成分」と呼ぶ。

全体 $N$ が偶数、$S+T$ が奇数なので、奇数成分は奇数個ある。
初手で、奇数成分の1つを先手の望む状態になるよう $S$ または $T$ にくっつけるとよい。 （奇数成分は偶数個になる）

後手が取り得る操作における、「$S,T$ の偶奇」「奇数成分の個数の偶奇」の変化を見ていくと、

• 浮いている成分同士をくっつける
  • →不変（たとえ奇数同士を繋げても、2個減るので偶奇は不変）
• 連結成分内の頂点同士を結ぶ
  • →不変
• 浮いている成分を $S$ や $T$ にくっつける
  • →偶数成分をくっつけても不変
  • →奇数成分をくっつけた場合、必ずまだ1つは残っているので、先手は変化を相殺するようにくっつければ不変

となり、後手は先手の勝ち状態を覆すことが出来ない。

残る問題は、「$S,T$ の偶奇を先手から先に変化させざるを得ない、そんな手しか残っていない」ようなことが無いかどうかだが、 そのような状況というのは、

• 連結成分が全て完全グラフ
• 偶数成分が残っていたらくっつける操作が取れるので、偶数成分は残っていない
• 奇数成分が残っていたら必ず偶数個残っていて、それ同士を繋げる操作が取れるので、奇数成分も残っていない

となり、結局これは最終状態に他ならない。よって、そのような機会は来ない。

初期状態の $S,T$ の偶奇が異なる場合は、先手必勝であることが言える。

$S,T$ の偶奇が異なる場合の 「初手で、奇数成分の1つを先手の望む状態になるよう $S$ または $T$ にくっつける」を行った後の状態である。

先手必勝。

先手、後手の立場が逆になる。先手が変化させようとしても後手に戻されるので、後手必勝。

Python3

F - Lights Out on Connected Graph