ABC138 E - Strings of Impurity
2020-04-11
精進記録 / 解法メモ
問題
解法
まず事前に s の各文字が出現する位置を、文字がキーな Map にソートされた vector で持つようにして適当に詰め込み、t の各文字について前から順になめて、一つ前に見た文字の位置以降で一番始めに現在見ている文字が出現する位置をにぶたんで探索しつつ i の最小値を求めた。
i の求め方は、一つ前に見た文字以降で現在みている文字が出現するなら一つ前の文字からの距離をiにプラス、存在しないなら一つ前の文字から s の末尾までの距離を足して、さらに s の先頭から欲しい文字が出現する文字の位置までをプラスする、みたいな感じでやった。
考察は事前知識はあんまり要らないタイプの問題だったが、実装が地味にバグらせやすくて
ﾒﾝﾄﾞｸｻｲちょっと大変だった。謎にTLEすると思ったら vector の参照のつもりのものがコピーになっていたという初歩的なミスをやらかしていて、気が付かずに結構悩んだ。
考察
サンプルを手で愚直に試した。試したところ貪欲にやればとりあえず解は求められそうなことはわかったが、何も考えずにやると になってヤバそうだったので、事前に各文字がどこに出現するかを文字がキーな Map にソートされた vector で持っておくことにした。
あとは取り出すときに lower_bound を使えば となって十分間に合うので、そのまま実装した。（出現位置から文字数を求めるところとか、実装が地味に面倒でちょっと大変だった）
ちなみに公式解説を見てからわかったが s を2つくっつけたものを用意しておけば先頭からとか末尾からとかを気にしなくてよくなり、ちょっと楽になる。そこまでは気が付かなかった。
以下サンプルを手で試したときのメモ。（汚い・・・）
以上。オワリ😇
