E - Cheating Amidakuji
取り除かったときの結果と比較して何かする、という方針は考えたのだけど、うまくいかないと思ってやめてしまった。
一つ取り除いたとき、最終結果とどう変わるか、と考えるのが重要だった。
……というか、考えなくても分からないと厳しくって。
一つ除いた場合とそうでない場合とを実験して比較して……というような手段を取れば確かに分かるのだろうけど、この問題はそこまでするような難しい問題ではないと思う。最終結果との比較でできるのかな？ と思ったら、解法のやり方でいけるのかな？ と思えて欲しいところ。
そう思えなかったのは、頭が働いてなかったということなのかね。
F - BOX
適切にUnion-findを使えば解けるということはコンテスト中から分かっていた。
が、実装難しくないですか？ 何を持てば良いか整理した後で、一時間以上実装にかかっている。
コンテスト中に通すのは厳しかった気がする。こんなに解かれているのが不思議。
G - At Most 2 Colors
自力AC。
「自分と違う色が最も最近現れたのはいつか？」を持てば二乗DPになる。そこから、累積和を使って（セグメント木を使うこともできそう）高速化する。
Gとしては簡単だし、今回のEやFと比べると簡単な気がする。Eは発想問題だから人によるかもしれないけど、Fよりは明らかに簡単では。
0 件のコメント:
コメントを投稿