roiti46's blog

主に競プロ問題の解説を載せてます

TopCoder SRM 656 Div2 Easy: CorruptedMessage

Div2Easyはさすがに簡単だ。

問題はこちら

問題

1つの英小文字からなるメッセージを送ったが、ノイズのせいでk文字が変化してしまい文字列sとなった。
元のメッセージとしてありうるものを1つ答えよ。元のメッセージの候補は必ず1つ以上存在する。

解法

文字列sに含まれる文字の出現回数を数えていく。
あとは (そのアルファベットの出現回数) + k == n を満たすようなアルファベットを探し、それをlen(s)回繰り返したものを返せばいい。

def reconstructMessage(self, s, k):
    n = len(s)
    hist = collections.defaultdict(int)
    for si in s:
        hist[si] += 1
    for si in "abcdefghijklmnopqrstuvwxyz":
        if hist[si]+k == n:
            return si*n

まとめ

ふつうのEasy問題だった

広告を非表示にする