【1日目】ABC182を解いてみる

1日目。

とりあえずAtCoderの過去問を片っ端からやっていき、分からないことが出てきたらその都度調べる…という方針でやっていくこととする。

まず手始めにABC182を解いてみた。100分かけて、バーチャル参加機能を使ってみる。 結果はこのような感じ。

A 0:59
B 7:25
C 21:39
D 36:00
E TLE
F 未回答

まずまずできたと思う。Bは少し時間かかりすぎな気もする。Eは前も似たような問題を見たことがある気がする…けれど解けなかった。Fは手を付けていないので後ほどやる。

A～Dは特に問題はなかったので、EとFを解説を見ながら再考。

E - Akari

atcoder.jp

解説を見るとあ、なんだそれだけか、、という感じがした。まあそれが自力で浮かばなければ意味はないのだけど。

計算量に関する考察力がまだまだ不足しているなと感じた。この問題においては、各マスについて定数回ずつの計算ならば、HW < 10⁶ なのでTLEにはならないのだが、そこで

各光源についてしらみつぶしに調べても、すでに分かっているマスをスキップさえすればO(HW)時間で探索できる

という発想ができるかがミソだったと思う。自分はこれがなかったな。

F - Valid payments

atcoder.jp

お釣りが返ってくることをマイナス枚払ったと見なすことで問題が単純化できるな…ということまでは思いついたが、そこで力尽きた。

DP難しい。なかなか思いつきそうで思いつかない。何をメモ化するのかをビシッと決めてかからないと難しい、のだと思う。何かモヤっとしたイメージ、くらいまでは独力で行くんだけど、何をメモ化すれば良いのかが分からない。いや、もしかしたらDPを使う、ということすら思い浮かんでなかったのかもしれない。いずれにしてもそこの壁を乗り越えてDPを使いこなせるようにすることが当面の目標かな。

明日は

• 今日のABC182-Fの残り
• ABC181(再びバーチャル参加)

をやる予定。