AtCoder Beginner Contest 207 反省
バカみたいな難易度配置のコンテストだったので一応温まったっぽい。
今日はちょっと頭ぽわぽわ気味だった。実装・立ち回りは今月中では一番悪いかもしれない。
結果を鑑みて
1100 58:15
295位となった。Cで手こずり、Dを捨てたり捨てきれなかったりして時間を浪費、脳死添字バグでEを解くのに時間をかけ、実装力のなさでFを落とした。奇跡的に冷えずに済んだ感じ。先週よりは忙しくないはずだが、実装・ムーブのミスが多く、危うく冷えるところだった。
A - Repression
ソートした。
B - Hydrate
可能かどうかを場合分け→二分探索？と踏んだ。
可能かどうかの条件が面倒そう、漏れが出そうに見えて犯罪二分探索するかちゃんと条件考えるか逡巡した。この時間がまず無駄だった。
結局、犯罪二分探索をした。上界を10^100で始めて、結果が10^100なら-1、それ以外になるなら二分探索の結果を出力することとした。どうせ答えは大きくともlonglongに収まるだろうと思うので、これで十分である。操作回数の自明な上界を見積もろうともしたが、これもなんだか面倒に感じてやめた。
今回は変数が4つあったので直観が働きにくかったのかもしれない。
少し時間かかって次の問題へ進んだ。
C - Many Segments
全部閉区間にしちゃおう！と思って、開区間なら内側へ1だけ縮めるのをして、サンプル1が合わなくて10分首をかしげていた。
よくサンプルの説明を読むと、これでは不十分なことに気付いて全体10倍して同様の処理を行なって通した。
この時点で600位くらいだった気がする。かなしい。
D - Congruence Points
問題読む前に順位表からヤバそうな雰囲気を察して、Eを先に読んだ。
この問題に似ていることを思い出し、平行移動不変量である重心座標系を使おうと思った。そこから何故か線形計算量で解けないかとか考えたり誤差を気にしたりして全然実装しなかった。
N≦100なのだし、「円上 格子点」でググったりもして解けそうなオーラもあったが、Fも解けそうな見た目をしていたためFに挑戦して夢破れてしまった。
E - Mod i
まあ二乗のdpが許されているのでそれをするのだが、遷移先の前計算がないと余計なlogが乗ったりしてまずpython系では通らない。
遷移の前計算はmod i 固定で累積和の剰余が同じ数になるものをまとめることによってできる。ここでsetやsortを使う必要はなく、基数ソートで足りる。もっと言えば、実際にソートする必要はなくて剰余ごとに1つのindexを格納するテーブルさえ持てば実装可能で、これは定数倍も小さい。
ここまで進んだはいいが、そのあとのdpで添字ミス（最後に空部分列を追加することを容認してしまっていた。）に気付かずに首傾げてえらい時間経ってしまった。
通した後順位を見てみると200位くらいで、DもFもパッと見取れそうな見た目していたので両方考えつつF重視で行こうとした。
F - Tree Patrolling
次数だけみればいいのかと思ったが、包除原理の計算量がでかすぎるので不適。であれば素直に木dpで、制約などからどうせ二乗の木dpだろと思って、三本の二次元dpテーブルをはやせばいいというところまではすぐに辿り着いた。
しかし、遷移が頭の中でぐちゃぐちゃになって結局解けなかった。
総括
復習は今度やることにしたい。今週もなんだかんだコンテスト練習をしていなかったのがムーブに現れてしまった。どこか自分のレートに対して他人事でふわふわした感情のまま取り組んでいたり、Cで手こずった後に明確に焦りを感じたのにも関わらずリフレッシュに時間を使わなかったのもよくなかった。
コンテスト練習をしないとムーブとリカバリーの勘が鈍るっぽい。典型90のおかげか、解法の勘はよかった。いつでも落ち着いて挑めるようになりたいね。
