AtCoder Beginner Contest 031 D - 語呂合わせ

問題文

http://abc031.contest.atcoder.jp/tasks/abc031_d

解法

サンプル1の入力を考えてみる。

356 migoro
461 yoroi
2 ni
12 ini

1番目の文字列の先頭を見ると、3に対応する文字列は"m","mi","mig"の3通りしかないことが分かる。たとえば3<=>"m"だったとしよう。

56 igoro
461 yoroi
2 ni
12 ini

1番目の文字列の先頭を見ると、5に対応する文字列は"i","ig","igo"の3通りしかないことが分かる。たとえば5<=>"ig"だったとしよう。

6 oro
461 yoroi
2 ni
12 ini

こんな感じに各文字列の先頭部分を見れば候補が分かるため、O(3^K)で探索できる。3^9=19683なので適当に実装しても余裕で通る。

AtCoder Beginner Contest 031 D - 語呂合わせ

感想

break書いてなくてTLEしたの良くなかった。