http://abc042.contest.atcoder.jp/tasks/arc058_a http://arc058.contest.atcoder.jp/tasks/arc058_a
概要
- N以上の数値で、与えられた数字を使わずに作れる最小のものを答える。
高速解法
- 使って良い数字の集合(入力の補集合)Aを求めておく。
- まず、与えられた数値の文字列表記Sの前から後ろに向かって、使って良い数字以外が含まれる桁jを求める。
- もし見つからないなら、Sを出力して終了する。
- 桁jから前側に向かって、Siよりも大きい数字がAに含まれるような桁kを求める。見つからなければ-1とする。
- 大きい数字がAに含まれるとは、繰り上がりを受け切れるという意味である。
- kが-1ならばAの先頭(ただし先頭が0ならば次の要素)を出力。0以上ならばSの先頭からk文字とSkよりも大きい数字のうち最小のものを出力。
- Aの先頭要素を(Sの文字数-k-1)だけつなげて出力。
- kを-1にしておくとこの部分での場合分けが不要になるというわけ。
- 2回Sを走査するので、計算量はO(S)あるいはO(logN)となる。
まとめ
- 土曜日、帰宅後に問題ページを開いて最初に思いついた解法がこれです。O(NlogN)解法の方が明らかに実装が楽なので、コンテストとしては負け。
- 復習コンテストのストックにしなかったのは、テストデータ作成が面倒だったからです。