AGC029 C - Lexicographic constraints
解法
種類以下で問題の条件を満たすような文字列たちを作成できるか？という問題を考えると、ある境界が存在し、それ以下では作成不可能、それ以上では作成可能になります。よって、ある
について問題の条件を満たすかどうか、を見ながら二分探索を行えばよいです。
先頭の文字列から順に見ていったときに、次に作成する文字列は、作成できる文字列の中で辞書順最小のものを選んだ場合が一番得をします。
なので、今作成し終えた文字列の状態を見て、次に作成する辞書順最小の文字列が何か？というのがわかればよいです。
文字列をランレングス圧縮のようにして、
文字目までが
という文字になっている
という情報で書き換えます。
すると、次に作成する文字列の長さがであったとき、
であれば、辞書順最小の文字を末尾に追加
そうでなければ、すでに作成し終えている文字列の末尾のうち、
以下でかつ
未満の文字を次の文字に置き換え、その後辞書順最小の文字で埋める
という操作をすればよいです。
上記の条件を満たすような文字が存在しなければ、作成できないということになります。
感想
初手で貪欲に走ったので反省…
