練習

Codeforces 62B - Tyndex.Brome

方針

O(n^2)は無理なので、比較元について、各文字の出現する場所をあらかじめ調べておく。例えば、「aは、1,3,10番目に出る」みたいな感じ。

比較先の各文字について、上の表を二部探索すればいい。

実装

STL の lower_bound, upper_bound が大活躍……のはずが、いろいろバグを盛りこんでしまい、自力では直せなかった。Practice で system test のログを見てやっと分かった。

lower_bound, upper_bound の意味は、言葉で説明しても(されても)分かりにくいので、自分でいろいろ実験してみるしかない。で、その時は分かっても、しばらくすると、また使い方を忘れる。

今回は、[1, 3, 4, 9, 10] みたいな配列があったとき、「5に一番近いのは?」といったクエリをこなしたい。原則は、lower_bound - 1 と upper_bound を見ればいい。問題は両端を見るときで、ここで場合分けが必要。それから、「4」みたいに存在するものを探したときは、lower_bound がそれ自体を指し、upper_bound はその右になるので、場合分け必要。

なんかゴチャゴチャしていてすっきりしない。うまい書き方があるんだろうか?