ABC131
こないだ Dinic 作り直したので、最小カットやるだけみたいな問題来てくれ〜〜〜
Problems
- A: ループにしようか迷ったけどべた書き
- B: さくっと実装しなきゃいけないときにこういうの出されると発狂する（思考停止全探索）
- C: B よりかんたん
- D: C よりかんたん
- E: 構成は見た瞬間に泣きそうになる・・・。まずサンプルを図示してみて、サンプルにはループがあるけど実は木に限っても問題ないことがわかる。木でたくさん距離 2 のペアを作るには・・・頂点を決めて子をたくさん並べたい気持ちになってくる。ウニだ！これで最大
ペア作れる。ジャスト K ペア作るには・・・子同士を繋げば 1 ペア減らせる。これ書けば通るんではって思ったけど、これほんとに上界かと言われると困る。
か。辺 1 本使うたびに距離 1 のペアができるので、これ以上はさすがに無理でしょ（←単純連結グラフであることを使えば自明なのに忘れている）。はい実装。しかし不安なので Warshall-Floyd を書いて検算する。グラフの構築間違えてバグり散らかした上に本実装のところは全部合ってた。
- F: わからん。。。
で長方形を作れたら軸
をマージしていい気がしていて、あとは連結成分を調べればいい気がしたけど
より速く実装できる自信がなかった。
Result
- 397th, 1596 (+21)
- あとちょっとで青だ
- 前回と同じぐらいの時間で E まで解いたのに順位結構落ちたなぁ。F がこんなに解かれるとは......
- 500 が安定して解けるようになってきたのはよくて、600 をちゃんと解けるようにならないとな
