ゆらのふなびと

競プロ, Python, C++

ABC009 C - 辞書式順序ふたたび

「いつものC問題より難しい」との注釈通り、わかりにくい問題だった。

問題

C: 辞書式順序ふたたび - AtCoder Beginner Contest 009 | AtCoder

長さNの文字列Sが与えられるので、元から位置の変わった文字の個数が K 以下であるような文字列のうち、辞書順最小のものを求めよという問題。

解法

www.slideshare.net

公式の解答をよく読んで実装する。

ポイントは

  • 辞書順最小を得るには、最初の方に小さいアルファベットを持ってくる
  • あるアルファベットをTに追加したとき、制約を満たせるか(今まで作った分の不一致数 + これから作る分の最小の不一致数 <= K であるか)

また、

  • 「これから作る分の最小の不一致数」=「これから作る分の長さ」-「最大の一致数」

である。(「最大の一致数」はスライドp.54にのっとり求める)

#count minimum num of mismatch
def count(T, c):
    #determined part
    s_done = S[:len(T)+1]
    t_done = T + c
    cnt = 0
    for i in xrange(len(s_done)):
        if s_done[i] != t_done[i]:
            cnt += 1

    #undetermined part
    same = 0    #num of match
    #from 'a' to 'z'
    for i in xrange(97, 97+26):
        x = chr(i)
        same += min(S.count(x) - s_done.count(x), S.count(x) - t_done.count(x))
    #num of mismatch = length - num of match
    cnt += (N - len(T) - 1) - same
    
    return cnt

N, K = map(int, raw_input().split())
S = raw_input()
order_S = sorted(S)
T = ""
for i in xrange(N):
    for c in order_S:
        if count(T, c) <= K:
            T = T+c
            order_S.remove(c)
            break
print T