ABC124 C - Coloring Colorfully

備忘録

問題

atcoder.jp

回答

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def func(S):
    tmp = ""
    ret = 0
    for s in S:
        if tmp == s:
            ret += 1
            tmp = '1' if s == '0' else '0'
        else:
            tmp = s
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = list(iss())
    ret = func(S)
    SS = S[::-1]
    ret = min(ret, func(SS))
    print(ret)


if __name__ == '__main__':
    main()

考え方

N枚のタイルに対して、1枚目から次のタイルと異なるか否かを試して、
色を塗る回数を調べる。
その後、N枚のタイルの逆から同様の処理を行って、必要回数が少ないほうを回答とした。

が、公式の解説とは全然違ったため、公式の解説に乗っ取った回答も一応しました。

Submission #11618779 - AtCoder Beginner Contest 124