AtCoder Beginner Contest 009 (辞書式順序ふたたび) を解いてみた

ABC 009 C問題に使われるアルゴリズム要素は貪欲法です。貪欲法自体は定型のアルゴリズムがあるわけではないので、知識ではなく地頭を問う問題です。

C - 辞書式順序ふたたび
- 解説：Abc009

問題文
- 文字列Sとその長さN、そして入れ替えしていい文字数Kが与えられる
- K文字だけ入れ替えて辞書順で最小になる文字列を求めよ

考え方

7 2
atcoder

の場合、２文字入れ替え可能。答えはactoderになる。文字列を前から順に見ていって、辞書順で最小になるようにすればよい。

疑似コード

解説にある疑似コードをもう少し詳細に書き下してみた

(解説の疑似コード)
T ← ""
for i in 0 to N-1
  for c in (使用可能な文字を辞書順で)
    if (T+cにして大丈夫なら)
      T ← T + c
      break

(書き下し)
def available(t)
    Sの文字列からtの文字列を除いてソートしたもの

T ← ""
for i in 0 to N-1
  for c in available(t)
    T ← T + c  // T[i] = c

    k = i文字目まででの変更数
    switch_count, t_tmp = 残り文字列を埋めた時の変更数と文字列を返す

    if k + switch_count == K
        t_tmpを表示して終了
    elsif k + switch_count > K
        # 次の文字を試す
    else
        # 次のiを試す
        break
    end