Submission #71259718

---

Source Code Expand

"""
<方針>
- 線形時間程度で収めることを考える。
- 連続する数字をブロックとして捉えて一旦まとめてみる。`O(N)`
- `1122` が `12` を包含するように、隣同士のブロックで作れる最長の長さが個数になりそう。
"""
# 入力
S = input()

# 番兵
S += "A"

# ブロックの文字を記録
chars = []
# ブロックの個数を記録
cnts = []

# 現在の文字
char = S[0]
# 現在連続している個数
cnt = 1

# 2個目以降をみる
for s in S[1:]:
  # 文字が一致すれば
  if(s == char):
    # 個数を増やす
    cnt += 1
  # 一致しなければ、
  else:
    # 現在の文字と個数をブロック単位として登録する
    chars.append(char)
    cnts.append(cnt)
    
    # 新しいのに変える
    char = s
    cnt = 1

# 個数計測
ans = 0

# 隣り合うところだけ見る
for i in range(len(chars)-1):
  # 左の数字に1足したら右の数字になるとき、
  if(int(chars[i])+1 == int(chars[i+1])):
    # 作れる最大の長さが個数
    ans += min(cnts[i], cnts[i+1])

# 出力
print(ans)

Submission Info

Judge Result