コンテストページ
Dwango Programming Contest 6th - AtCoder
解法
✔A - Falling Asleep（200 点）
X の入力が最後なのが厄介ですから、vector
✔B - Fusing Slimes（600 点）
左から i 番目の区間をスライムが通る回数の期待値は、1 + 1 / 2 + ... + 1 / (i + 1) です。
✖C - Cookie Distribution（800 点）
手も足も出ませんでした。悲しいですね。
✖D - Arrangement（800 点）
サンプル 2 の場合以外は構成可能です。
答え
次の規則で選びます。
- 残り 3 つで、循環参照しているものがあれば、それらのうち選べるもののなかで小さい方を選びます。
- 自分以外のすべての頂点によって参照されているものがあれば、それを選びます。
- そうでない場合は、もっとも小さいものを選べるなら選びます。無理なら 2 番目で妥協しましょう。
規則 2 で「選びます」とありますが、選べること
消せないとすると、前に消した頂点に参照されていることになります。しかし、ということはもう 1 手前から集中していたことになります。そうすると、1 手前の時点でも集中していたことになります。ならばそのときに消えていないとおかしいです。なぜおかしいかと言うと、3 点以上あるときには集中する点は 1 つまでです。追いつかないはずがありません。
これで詰まないこと
この規則で選んで詰んだと仮定します。操作不能な状態は、1 点しか残っていなくてそれが選べないときです。2 点のときはどうだったのでしょう。2 つの場合があります。
- 循環参照をしているか
- していないか
です。
前者の場合は、まずサンプル 2 の場合は救いがありませんね。そうでなければ残り 3 つのときに頑張ればなんとかなって、実際規則の 1 つ目によって循環参照は（この時点で高々 1 つですから）解決します。
後者の場合、片方がもう片方を参照しているものの、適切な方を選ぼうにも選べないという状況です。こちらは残り 3 つの時点で、2 つの参照の集中していることになります。したがって規則 2 から、2 つ時点では参照がなしになって平和です。
これが最善なこと
残り 3 つのときを考えます。このとき循環参照は絶対に残しては行けないので、それを壊しに行きましょう。集中点がある場合を考えます。集中点を放置すると、最後まで消せなくて困ります。
ちなみに
なんか最後の3つくらいはよくわからないことになるのでそこだけ全探索する必要があります
— てんぷら (@tempura_cpp) 2020年1月11日
このあたりの手の抜き方は、本当にてんぷらさんはお上手だと感じます。
結果
362 位、1880 青パフォです。
