今日解いた競プロの問題。

競プロ典型90問-083: 解説AC。平方分割は全然分からないので諦めて解説見て正解だった。今回のでちょっとだけ平方分割の気持ちを掴んだ気がするので、もっと類題を解いて感覚を掴んでいきたい。

「愚直に全ての隣接頂点を更新する」のと「その頂点だけ更新して時刻を記録し、取得時に全ての隣接頂点を見る」という2通りの策が思いついたが、どちらにしても最悪クエリ$O(M)$かかってTLEする。しかし(あくまで大雑把な気持ちであるが)「良い感じに間をとる」ことで$O(\sqrt{M})$に抑えることが出来る。

最近解説ACして印象に残っていたARC139-Bも似たような発想だった。現在の自分が何も思いつかない問題には結構これが含まれているのかもしれない。ちゃんと発想の道具として身に着けたい。

とにかく「こういう感じにするとこういうケースでTLEする」「逆にこういう感じにするとこういうケースでTLEする」という2つの戦略があるときに「都合のいい方を選ぶ」「いい感じに間を取る」というのが大雑把な気持ちだろうか。ちょっとまだ飲み込み切れていない感じがするので何度も反芻して血肉にする。

---

新サイトのデザインを進めた。割と良い感じになってきた。トップページやハブ系のページのデザインは大体出来てきたので、あとは記事を表示するところのデザインをさっさと完成させたい。コードとかをそれらしい枠で囲んで表示するようにしたい。

あとデザインは良いのだが画像が少なくて殺風景なので、もうちょっと画像を積極的に入れたいなと思った。