AtCoder Beginner Contest 009：C - 辞書式順序ふたたび
問題
https://atcoder.jp/contests/abc009/tasks/abc009_3
考え方
ヒントの通り。辞書順最小を目指すときは、文字列の先頭から順にできるだけ最小になるように文字列を構成することになる。実際に文字列の の
番目の文字を
としたとき、残りの文字列で
個以内の条件を満たすように
を構成できるとすると、
番目の文字が
で確定する。
このようにして 文字目まで文字列を構成すれば条件を満たす辞書順最小の文字列を構成することができる。
Submission #4032572 - AtCoder Beginner Contest 009
どこに着目して考察するべきだったか
辞書順最小は先頭から順に最小になるように構成する。また一旦可能性を全探索して、条件を満たせばOKという考え方が重要っぽい。
何がバグっていたか
得た知見(典型ポイント)
- 辞書順最小は前から貪欲に求めることができる
- 候補を全探索して、条件を満たすかどうか判定する
- 徐々に解を絞り込んでいく
