Loading [MathJax]/jax/output/CommonHTML/jax.js

目次

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

AtCoder Regular Contest 105

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

C - Camels and Bridge

C - Camels and Bridge

問題

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

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

解法

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

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

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

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

ラクダの合計体重が 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つの区間の上に同時に乗りうるラクダは、隊列の中で連続している。左端のラクダを cl、右端を cr とすると、その間の合計体重が分かる。

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

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

計算量は、関係性の配列に O(MlogM)、最小距離を求めるのに O(N!N2logM) となる。

Python3

D - Let's Play Nim

D - Let's Play Nim

問題

解法

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

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

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

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

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

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

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

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

一般に、A xor B=A+B2(A&B)A xor BA+B なので、 X が過半数なら X>A+B+C+...A xorB xor... なので、X 以外の数のXORで X を作りたくても無理。

Python3

E - Keep Graph Disconnected

E - Keep Graph Disconnected

問題

解法

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

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

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

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

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

N が奇数の時

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

代入すると S(SN)+N(N1)2 となり、S(SN)N 奇数の時は必ず偶数となる。
よって S によらず N だけで偶奇がわかる。

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

N が偶数の時

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

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

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

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

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

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

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

S,T の偶奇が異なる場合

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

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

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

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

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

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

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

S,T の偶奇が同じで、先手勝ちの状態の場合

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

先手必勝。

S,T の偶奇が同じで、後手勝ちの状態の場合

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

Python3

F - Lights Out on Connected Graph

F - Lights Out on Connected Graph

問題

解法

1