AtCoder Beginner Contest 229 反省
メンタルが壊れる!
結果を鑑みて
1500 19:12
542位。Fで詰まって、Gに行くのが遅すぎた。今回のFが解けないのは本当にヤバい。
A - First Grid
よく考えるとNoのパターンが斜めに2個配置の2パターンしかない。
B - Hard Calculation
がんばって実装する。10で割っていけば良いのだが、0埋めしたlistでやってしまった。筋悪。
C - Cheese
貪欲。
D - Longest X
にぶたんで解いた。
このあたりまでは100位ちょっとくらいで通過していたので余裕をもってEへ進めた。
E - Graph Destruction
UFくさいし、カットしてから辺を追加しないのでクエリ逆読みだと気付いた。
あとはよしなにやる。
トイレ行っている間に抜かれて200位くらいになってた。
F- Make Bipartite
一般グラフだとNPらしいし、dpくらいしかないんだよな。
嘘解法としてMST→くっつけられるだけ辺をくっつけるとかがあって、これだと一般グラフでも解けることになっちゃわないか?と思いながら提出してしまった。バカすぎる。
素直にdpすればいいのに長さ3の奇閉路をとらないグラフを構築するようにdpした。ふつうに落ちて、悲しいしもうわけわかんなくなってGへ行った。のこり40分弱くらい。
今考えても時間使いすぎだと思う。
F通さないとヤバいのはそうだが、詰まってるときは別の問題通してから帰ってくるっていうのは定石ムーブのはず。
G - Longest Y
まず、ある地点より右にあるYを寄せていく解法を作った。これ15分はかかったはずだけどサンプル1見れば嘘だと言うことがわかる。視野が狭くなっていた。
同時にサンプル1が解法を端的に表していることに気付き、結局あと10分くらいしかなかったから通せなかった。考察は合っていて、終了後10分あたりで通せた。
総括
ABCにだらだら参加して、ARCはnosubばっかりしてたから詰まった時のムーブを忘れていた。8問制だから6問のときよりも問題を保留するかどうかの見極めが重要かもしれない。
これでARC出て大丈夫なのかなあ