ABC124 C - Coloring Colorfully から学んだ

5135 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク



シンプルに "0" から始めた場合、 "1" から始めた場合、
交互になってない箇所をカウントして比較する。最小を output すれば良いはずです。

ColoringColorfully.py
S = input()

cntst0 = 0 #"0"start の場合
for i in range(len(S)): # 計算量 O(N)
    if i%2 == 0 and S[i] != "0":
        cntst0 += 1
    elif i%2 != 0 and S[i] != "1":
        cntst0 += 1

cntst1 = 0 #"1"start の場合
for j in range(len(S)):# 計算量 O(N)
    if j%2 == 0 and S[j] != "1":
        cntst1 += 1
    elif j%2 != 0 and S[j] != "0":
        cntst1 += 1

print(min(cntst0,cntst1))#計算量 O(2)

#合計計算量 O(2N+2)

極解を見つけた。

abc124c.py
S = input()
cnt = S[0::2].count("1") + S[1::2].count("0")
print(min(cnt,len(S)-cnt))

#000 の場合
#cnt = 0 + 1 = 1
#len(S)-cnt = 2
#ans = min(1,2)

っと言う事らしい。んー、自分には少し早いようだ。