ABC468 参加記

2026/07/25

私です。

ABC468 に参加しました。3ペナ激遅4完です。久々に負けました。今回のWriterさんにレートを返してもらえるまで許せません。

とはいえ、今回の C 問題は勉強になったので、ギリOKとします。

誤読をしており、極大値の個数を求める問題だと気付くまで、出遅れました。

誤読をしており、なぜか $D = 1$ だと思ってました。出遅れました。

G の前後 $D$ 以下のグリッドを埋めて、空いてるマスの個数を数えると良いです。

さて、問題のC問題です。

順列全探索であることは2秒で見抜けたのですが、そこから実際に解くまでに時間をかけすぎました…

最初は先頭の数字で条件付けてこねこねしていたのですが、2ペナを出してもなお解ける未来が見えず、一度考え直してみると、順列を数値に直すと解けることに気付き、解くことができました。

$[1, 3, 2] \to 132$ みたいな感じです。

そして、コンテスト後に発覚したことなのですが、Rustでもタプルの比較ができるそうで、私の2ペナは一体…

なので、知ってさえいれば、ある順列 $A$ に対して、 $P \lt A \lt Q$ を満たす個数を求めるだけの問題に成り下がっていた、ということです。

$|S| \le 10^4$ なので、 $O(|S|^2)$ で通るのは自明で、全探索で瞬殺！と思って書いたコードが見事に $O(|S|^3)$ で本当にこういうところだよなぁと…

なぜか、TLE が出るなぁと思ってコードを見ると普通に $O(|S|^3)$ でした。皆さんはちゃんと計算量に気をつけてくださいね。

そこからは、Manacherアルゴリズムみたいな動きをすると解けるなと思い、ライブラリのManacherをガチャガチャしたのですが、うまくいかなかったので、 1から書きました。

うまく言語化はできないのですが、こういう二重和とかの問題は横で見るのではなく、縦で見るとうまくいくイメージがあり、それを良い感じに具体的にしたかったのですが、普通に解けませんでした。

式変形の問題が大抵解けていないので、だいぶまずいなぁ…と思ってます。

最後に

今回で弊サークルから水色コーダーが誕生しました。とてもめでたいことです。

私もここまで単調増加で200弱稼いできましたが、綻びが出てきました。

まだここで止まるわけにはいきません。精進しようと思います。

とりあえず、典型90問を下から埋めていこうかな。

では、また。