脳log[20221019]

2022年10月19日 (水) [AtCoder] 精進。先週末にあった ABC273-F「Hammer 2」(黄 diff)。当日は終了直後にプライオリティキューを使った愚直シミュレーション解を投げて TLE を食らっていた>提出 #35695089 (TLE×28/AC×74)。実は TLE の背後に WA が隠れている。今日はもうちょっと手をかけて効率的にシミュレーションをするようにしたところ AC が出た。■提出 #35789620 (AC / 1898 Byte / 63 ms)。方針はこう。スタート地点から左右２手に分かれて駒を進めていく。右へ進んだ駒が壁にぶつかったら、その壁に合うハンマーを手に入れるのにどれだけ移動する必要があったかを左に進んだ駒に尋ねる。ハンマーにぶつかったら、逆に左に進んだ駒に教えるために現在の移動距離(+原点に戻るまでの距離)を保存する。左右どちらの駒もそれ以上進めなくなるまで交互に進めていく。工夫のしどころは壁の並びに合わせてハンマーに序列をつけることと、序列順に並べたハンマーの揃い具合をキーにして移動距離を保存したところ。揃い具合というのはビットフラグそのままではなくて、手前から何番目の壁まで漏れなく対応するハンマーが揃っているか。事前準備もいろいろやった。まず、ゴール(X)より後ろにある壁と対応するハンマーはないものとする。壁と対応するハンマーがスタート地点から見て同じ側にあって、ハンマーの方が手前にあるときもないものとして良い。ゴールより手前にある壁であって、対応するハンマーがその壁の向こうにあるものがあれば到達不可(-1)。このような事前準備をする意味は、壁もしくはハンマーにぶつかったとき、それは必ず反対側に進んだ駒に関わるものだという状況を作ることにある。一部例外はあって、ゴールと反対側にある絶対に通れない壁(とその向こうにあるハンマー)は判断を保留して残したけども。これが嘘解法だったらもう知らない。計算量のオーダーが狂っていて非常にありそうではあるけれど。左右への移動回数の合計が N 以下で、その中にあるループで書き込む移動距離の総数も N 以下。でも Bignum の桁数が N 以下だから結局 O(N^2) になるのかな。■「アライグマ「F問題は区間DPなのだ！ DP[L][R][f]=いままでにいったことのある左端がLで右端がRでいま(f?右端:左端)にいるときの移動距離の最小値 とすればいいのだ！」」 わからないのだ！ F 問題あたりにあって DP っぽいけど解けないなーって問題がだいたい区間 DP だと最近気がついたのだ。■自分の解法の O(N) の部分を上手くやる方法がないかなあ、ないかもなあとちらちら考えている。それというのは、ランダムなビットを立てていく、だけど決まった順番で立てていくときに、そのときどきで最も右にある 0 のビットの位置を知る方法。今は N 桁(≦1500)のビット演算でやっている。これをやる LIS のような、あるいは BIT を使った上手いやり方がないものかなあ、と。ビット演算で上手くやる類の問題だということがショートカットの不在を暗示しているような気がしている。……。いやいや、普通に右端の 0 の位置を覚えておいてその 0 が埋まるたびに次の 0 を探すようにすればループ全体で長さ N をなぞるだけになる。■提出 #35802156 (AC / 1813 Byte / 63 ms)。元が Bignum の定数倍の良さに助けられてほとんどインタープリタ起動のオーバーヘッドのみの時間だったので、63 ms から良くはなっていないけど、O(N^2) から O(N) になったのではないかと思う。あとは嘘解法でなければ。■解説放送「パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273） - YouTube」で 区間 DP から先の考察をやっていた！ 壁すら取っ払って必須の(折り返ししなければいけない)ハンマーを左右交互に取るところまで突き詰めていた！ それを前提にしてさらに先へ行こうとしていた！ でもこういうのって聞かされても理解できはしないんだよなあ。■提出 #35802759 (AC / 1819 Byte / 62 ms)。String#index メソッドに第２引数を渡し忘れるミスで O(N^2) になっていた。今度こそ本当に O(N) のはず。タイムも間違いなく誤差だけど 1 ms 縮んでいる。■あ、事前準備でソートが避けられないから O(NlogN) にはなるのか。解説放送(まだ見てる途中)でも O(N) だとは言ってなかったしな。