AtCoder Beginner Contest 210 反省

久しぶりにちゃんと出た。いろいろ忙しかったので......(と言いながらこの前tourist出しして-60した！！！)

1500(5) 119:40

509位となった。Dまでは良かったが、Eで解法ガチャをミスって破滅してしまった。何とか通したがえらいペナつけてしまった。

キャベツやさん！？

入力が多くて嫌だけど普通にif文で解けた。

中学生のころ、教室にあった百人一首のやつで坊主めくりしてた......

前から見るだけ。

エ、区間種類数クエリっていつぞやのF問題で出なかったか？と思ってびっくりしたが、固定区間長なのでふつうにやるだけだった。

この時点での順位はまあ良好だった。

なんとなくMSTぽいなと思ったが、全点被覆ではないのでただの最短経路だった。

左右で累積max、それを上下に累積maxしてやれば良いことに気付いた。実装自体はしんどかったが似た処理を4回書いただけだったのでバグらず通せた。

この時点で150位くらいで、焦らず進むことができた。

最初、これをグラフではなく整数論の問題だと直観した。これは半分当たりで半分ハズレだった。整数論だと考えると自然とgcdを利用する方法が生えるが、ここで誤解があった。

N=6のときにa=2の辺は0-2-4で2本しか張れないと思っていて、この解法だと約数系包除のような面倒くさいことをして計算しなければならなくなる。散々ペナをつけ、残り15分というところで過ちに気付いた。

グラフの問題として考えると、MST構築の貪欲性が鍵となる。常にコストの小さい辺を繋げれば良いので、コスト最小の辺でN - gcd(N, a)本繋ぐと問題が縮小してN = gcd(N, a)のときの同様の問題を解けば良くなる。再帰でACした。

かなり暗礁に乗り上げたような感じだったが、これはちょっと見た瞬間に解法が生えてほしかった...... 約数+グラフ系の問題は約数包除もそうだけどあまり得意じゃないかも。類題をあまり解いてこなかったせいか。

2-SATっぽいとは思ったが、辺の数が多いのでどうしたものかと思っていたらコンテストが終わった。

復習が結構たまってきた。夏休みに入れば時間もあると思うので（研究はしない！w）しっかりとレートを戻していきたい。まずは鈍った勘を何とかしよう！

perarduaadastra