AtCoder Grand Contest 016 A – Shrinking をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Grand Contest 016 A – Shrinking

実装の際、Pythonだと文字列操作が充実しているので楽をしやすい。ここでは string.split() を使用して簡潔に書いてみた。

# AtCoder Grand Contest 016 A - Shrinking
# https://atcoder.jp/contests/agc016/tasks/agc016_a
# tag: 文字列 文字列変換 考察 すぬけ君

# ある単一の文字 c にまとめることを考える。
# c と c の間に文字が入っている時、
# c ? ? ? c → c ? ? c → c ? c というように、
# 間は一文字ずつ縮まっていく。ちなみに文字列の端も同様で、
# ? ? c → ? c → c となっていく。
# したがって、c と c の間が一番広い部分をみつけ、
# そこと同じ回数だけ操作を行う必要がある。

def main():
    s = input()
    # 使われている文字のセットを作る
    ch_set = set(c for c in s)

    result = len(s)
    # どの文字に統一するかは全探索する
    for c in ch_set:
        # splitを用いて分割し、一番長い部分の長さを求める
        tmp_r = max(len(p) for p in s.split(c))

        if tmp_r < result:
            result = tmp_r

    print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。