ABC 401-500/ABC452C - Fishbones - 競技プログラミング用 知識集積所

---

問題

ABC452C
「魚の骨」というタイトルに騙されてはいけない。
普通イメージする魚の骨の形は全くしておらず、このオブジェに頭と尻尾部分は存在しない。
入力例のところでまるで脊椎の文字がさらに上下に続いてもよいかのように太線が引かれているのは完全に嘘情報である。

必要知識

B以下レベルの内容は省略

• メモ化※

考え方

問題の指示通りにやろうとすると、M個の文字列のN個の文字それぞれについて、M個の文字列を見て回ることになりTLE。
そこでメモ化※を用いる。

この問題では、「A文字ある文字列のB文字目にこの文字があるやつ、だれかいますか？」という形の質問を大量に答えることになる。
しかし質問の種類は、AとBの組み合わせが55通り、文字種が26通りしか存在せず、かけて1430通りしかない。
つまり、これら1430通りの質問の答えのカンニング用メモを事前に用意してしまえば、M個の文字列のそれぞれについて

• 文字列の長さをチェックする
• 問題なければ、各文字それぞれメモをカンニングしてチェックする

でよい。
M(N+1)=220万なので、これなら余裕をもって間に合う。

カンニング用メモの形はいろいろある。
i文字ある文字列のj文字目に文字cがあるかを

• vec.at(i).at(j).at(c-'a') にもつような、bool型の三次元vector※
• mp.at({i,j}).contains(c) で判定できるような、map<pair<int,int>,set<char>>

など。
いずれの形でも、先にM個の文字列の各文字を事前に一周して、単純に該当部分をtrueにしていくだけでよい。

解答例

解答例

注意点

脊椎のはみだしは禁止

問題リンクのところに書いたように、脊椎の文字が前後にはみ出ることは禁止されている。
頭側はB[i]の条件を読めば禁止らしいことがわかるが、尻尾側がダメなことはかなりわかりにくい。
「脊椎に書く文字列の長さは N である。」がひっそり書いてあるのを読み落とすと、入力例の絵ではむしろ逆の条件なようにも見えてしまうため、注意が必要。

別解

脊椎上にデータを置く

各文字列、Aの中に該当文字数のものがあるかどうかを探し、「ここにこの文字がほしければ担当できる」を書き残していく方法もある。
この場合は、文字列の数×脊椎の長さという意味でO(MN)となる。
解答例