String Equivalence
パナソニックプログラミングコンテスト2020-D "String Equivalence"
リアルタイムでこのコンテストには参加していて当時は苦しんでいた問題でした.
過去に苦しんだ分,今回は30分ほどでAC!
提出コード
考察
位置と文字の種類だけに着目して辞書順で若いものを出力する問題です.
例えば,"aaab"と"aaac"は「1~3文字目が同じで4文字目だけ違う」という共通点がある(条件を満たしている)ので同型です
位置と文字の種類だけを見ればいいので,文字列"a"の後ろに条件を満たすように文字を追加していけばよいです.
そこで,僕は下のような図が思い浮かんだのでキューを使って実装しました.
今見ている文字列に何種類文字が出てくるかで追加できる文字が変わってきます.
例えば,"aba"では2種類の文字が出てきますが,このときは末尾に"a","b","c"を追加出来て"abaa" ,"abab","abac"を新しくキューに追加すればOKです.
また,"abc"では3種類の文字が出てきますが,このときは末尾に"a","b","c","d"を追加出来て"abca","abcb","abcc","abcd"を新しくキューに追加すればOKです.
要は(登場する文字の種類)だけ末尾に追加できるということですね.
感想
今回はキューを使いましたが,再帰とかでも書けそうな気がしますね.
キューとかスタックとかのデータ構造が少しずつ使えるようになってきたという気持ちになれました.