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

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です