N文字のSがあり、そのインデックスを表す整数の組i,jがあるとして、
i,jは同じ文字、かつi,jの距離はL以上R以下、そんなやつをSの中から探索する。
Nは5×105、普通に探索すると間に合わない。
解説
ほぼ問題文の通りに求める素朴な解法では、解は合っても制限時間に間に合わない。
のでjを固定し、i側にlとrの範囲を押し付ける必要がある。具体的にはjを探索しながらj-R番目の文字でインクリメント、j-r-1番目の文字でデクリメントする。
このように、LとRの範囲内になる各文字種の数をjを探索しながら更新する。そのうえでj番目の文字のカウンタの数を順次答えに足していく。
そうしてカウンタをjの探索状況に絡めて更新しながらj番目の文字種のカウンタを参照すると、それがjと同じ文字種かつ範囲内にあるi,jの組み合わせの数を表す。同じ組み合わせをカウントしてしまう心配もない。
これでlとrの範囲内にあるi,jの組み合わせの数を求められる。
問題文のままiを固定する方法でもやれるが、前準備と終了条件が煩雑になるのでjを軸に探索、続くiがlとrの間にあるかどうかを考えたほうが効率が良い。
公式解説動画や実装例では、上記のような公式解説の下段にある解法で求めているが、少し違うのは文字種の扱い方。実装例では文字コードとして扱われるchar型をベースに0～25のインデックスを計算し、動画ではオーソドックスにmapを使用している。
グラフィカルな説明は公式解説動画が分かりやすいが、簡単に言うと、jを固定するとそれに応じてiも一定の範囲で引っ張られるので、jが1動けばiの範囲も1動く性質がある。iとなりうる範囲にどんな文字があるかは、iの範囲左側の文字をデクリメント、iの範囲右側の文字をインクリメントすれば、範囲内にある文字種毎のカウンタが出来上がる。
ここでiとなりうる範囲左側の位置を表すのが「j-R」、右側の位置が「j-L」。範囲から外れたものをデクリメントしたいので、左側は「j-R-1」になる。
感想
分からん分からんで頭一杯になってた。いわゆる式を変形してより分かりやすい形に考え直せばよかったのか、と。
コンテスト中はその考えも過ったけど、jを固定したとて結局iがLとRの範囲内にあるかを判定しないといけないんだからさして変わんなくないかとか思ってた。
なんとなく、各文字種毎にカウンタがあれば良さそうに思えたけど、データ構造に対する下準備をどうすべきかで頭が真っ白になって何も思いつかなかった。
完全に視野狭窄というか、ううん……反省。
コンテスト中にこの解法に辿り着ける気がしない。
コメント