ABC433 C – 1122 Substring 2

C - 1122 Substring 2

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

この問題はランレングス圧縮を使って解くことが出来ました。

以前ランレングス圧縮を使って解いた問題⇩

ひびのまなびろぐ

日々の学びや趣味をシェア。IT、ロードバイク、暮らしの工夫を発信中。

hibi-manabi-log.com

同じ文字がどれだけ続くかが肝になるなと思ったので、ランレングス圧縮の考え方を使って、対象の数字と連続する個数をもつ配列を作りました。

入力例1のように1122のような入力の場合1つ目が個数、2つ目が対象の数字として持つと下のような配列なります。

array = [[2, 1], [2, 2]]Code language: PHP (php)

あとは前後の数字が条件（前の数字に1足すと後の数字と等しい）に当てはまった場合、前後の数字の最小の個数をカウントしていきます。

上記の場合は、1も2も個数は2個なので、答えは2になります。

以下でACできました。

def i_map(): return map(int, input().split())
def i_list(): return list(map(int, input().split()))

s = list(map(int, list(input())))

tmp = [[s[0], 1]]
for i in range(1, len(s)):
  if tmp[-1][0] == s[i]:
    tmp[-1][1] += 1
  elif tmp[-1][0] != s[i]:
    tmp.append([s[i], 1])

ans = 0
for i in range(1, len(tmp)):
  if tmp[i-1][0] == tmp[i][0]-1:
    ans+=min(tmp[i-1][1], tmp[i][1])

print(ans)
Code language: Python (python)