2025年08月17日 (日)[AtCoder] 精進。昨日あった ABC419-E「Subarray Sum Divisibility」。コンテスト中の提出は TLE だった (#68558616)。制約が N,M,L≦500 で３乗だからしかたないな、C++ で書き直そうかな、やりたくないな、他に方法がないかな、やりたくないなと思いながらちまちま翻訳していたのだけど、デバッグの時間が数分足りなかった。ところがね、どこかの参加記を読んでいたら３乗ではないらしい。オーダーに L が関わってこない。自分の TLE 提出の 7 から 12 行目が諸悪の根源だった。点の遷移を線に展開することで結果としてオーダーが悪化していた。■提出 #68602921 (AC / 552 Byte / 56 ms)。３段構成。最初に L ずつ離れた要素の mod M を揃えるための最小操作数を求め、その結果長さ L の連続部分列の mod M がいくつになるかを求め、ついでに mod 調整用の遷移リストのリスト(L グループに分かれた N-L 個の遷移)を用意した。次にそれら３つを使って DP をして、長さ L の連続部分列の mod M を 0 から M-1 にするのに必要な最小操作数を記録した。最後に M 個から答えを選んだ。たぶんだけど mod M が 0 のところにだけ答えがあるのではなくて、1 から M-1 のところにも答えがあると思う。これらを 0 にする遷移は簡単で、mod を１増やすのに N/L のコストがかかる。これはつまり同時に操作しなければいけない L ずつ離れた要素のグループのサイズというのが１種類(N が L の倍数のとき)か２種類(N が L で割り切れないとき)あるのだけど、その小さい方のサイズがコスト。２番目のステップによってグループ内のすべての要素がグループ内のどれかの要素と同じ mod M へ揃えられているので、最後のステップではグループ全体の mod を同時に動かす。TLE になった原因はステップ２とステップ３を分けなかったことにあって、グループの mod をグループ内のどれかの要素に揃えるのではなく、M 個のどの値に揃えるケースについても考えていた。これだとステップ３はいらないけどオーダーが悪い。N と LM の違い。他の人の提出を見て気がついたけど、ステップ１とステップ２を分ける意味はなかった。２と３を分けないせいで TLE になって、今度は分けすぎていた。■制約でお手軽に殺されたのかと思っていたら、しっかり骨太な問題だった。こういう問題はじっくり日をまたいで考える必要があります。解けない。言語によっては 500 の３乗でも通ってたよってのは関係ない。Ruby できっちり 72 ms で通している人がいた (#68564921。HalMat さん。いつも難読だなあ文字を費やしても読みやすくはならないんだなあと思いながら拝見しています)。ここまでできてしかるべきだった。