AtCoder Beginner Contest 211 反省
今月の橙パフォです......
結果を鑑みて
2100 78:13
70位となった。Eまでそれなりに良いペースで解き続け、Fの重実装をバグらせず通すことができた。よかった......。直前のバチャではぐちゃぐちゃだった。
A - Blood Pressure
血圧。こんなのあるんだ〜という感じ。
見るからにコーナーケースなしなのでふつうにやった。
B - Cycle Hit
setの比較をした。
C - chokudai
耳dpをする。ほぼこれと同じ問題が典型90で出ていたはず。
とはいえこのレベルのdp数え上げもABC-Cに置かれるようになったか。
いつもならこのへんで順位表を見ているが、今回は見ていない。
D - Number of Shortest paths
BFSの遷移に場合の数を持たせた。第一感でこの解法を思いつくことができた。証明はしていないが、確かBFSは visited だけ管理できれば暫定距離の比較なしに距離更新をしていいというのがあったはずで、この更新順にのっとれば場合の数も遷移できよう......くらいに思っていた。
証明: AC
このあたりで順位表を見るとだいたい60位くらいで、安心して進むことができた。
E - Red Polyomino
第一感として、上からbitDPしていくというのがあった。しかしながら、連結性の情報をどう持たせるかが難儀だった。
始点を適当に決めてDFSするような形で構築を試みると、各状態から遷移は3方向しかないから実は愚直が答えじゃん!(嘘)というひらめきをして構築のコードを書いた。
ぎっちり書いた後、本当は各状態からの遷移方向は3通りどころではないということにサンプルを見て気づいた。仕方がないので枝刈りしながら遷移方向を増やすと、案外高速だった。
(本当はサンプルにヒントがあって、最大ケースの答えは60000通りしかない。枝刈りをちゃんとやれば高速)
これを通した時点で50位くらいだったかも。結構余裕を持って進むことができた。
F - Rectilinear Polygons
サンプルを見ないとなかなかイメージが難しかったりして、矩形に分解しまくってimosとかか?などと思ったりした。imosになる気がしたのはなんとなく半開区間っぽいクエリだったから。
あながち間違いではなくて、結果的にはBITを用いたインラインなimosだった。
各頂点が領域の始端か終端かをイベントソート+BITなどで判定できる。具体的には、y座標の昇順で見てその中でまたx座標の昇順に見て、頂点がすでに+1領域に含まれるならその頂点は-1とする。そうでないなら+1、というふうに。
頂点の寄与が+1か-1かがまるで偶奇のようにすぱっと決まって、それでimosができるのがなかなかきれいだった。バグらせなくてよかった〜
総括
とりあえず研究に人生を破壊された結果溶かした100近くのレートをほとんど回収することができた。よかった。今回のムーブはまあそれなり。勘が良かったのでムーブに左右されるような感じにはならなかった。