FreeStyleWiki

AtCoder Beginner Contest 009

[競技プログラミング,競プロ解説]

AtCoder Beginner Contest 009 - C

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

  考え方

7 2
atcoder

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

  • 7,2の場合
0 1 2 3 4 5 6
a
a c
a c t
a c t o
a c t o d
a c t o d e
a c t o d e r

疑似コード

  • 解説の疑似コードともう少し書き下したもの
(解説)
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)

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

    if k + switch_count == K
        t_tmpを表示して終了
    elsif k + switch_count > K
        # 次の文字を試す
    else
        # 次のiを試す
        break
    end
  • 使用可能な文字は関数で毎回算出するほうがよさそうだ
  • rubyコードにしてみる

+ ソースコード