PythonでJOI難易度5を埋める #26 - taxfree

IOIOI

文字列を逐一数えるのは面倒なので，"I"と"O"が交互の並び条件を満す長さの列を調べる． "I"と"O"が交互に並んでいるかはflagのT or Fで判定(一つ前が"I"ならT，"O"ならF)．

n = int(input())
m = int(input())
s = input()

cnt = 0
flag = False
ans = 0

for i in range(m):
    if flag:
        if s[i] == 'O':
            cnt += 1
            flag = False
        else:
            cnt = 1
    else:
        if s[i] == 'I':
            cnt += 1
            flag = True
            if cnt >= 2 * n + 1: #条件の判定
                ans += 1
        else:
            cnt = 0
print(ans)

20行目の判定について
(cnt - 3)は連続する" IOIOI $\dots$ "から最初の"IOI"を引いた個数，(cnt - 3)を2で割ったものが"IOI"に"OI"を足した回数． $\frac{cnt - 3}{2} \geq n - 1$ の場合は連続する文字列の左側から"IO"を引けば条件を満たすので， $\frac{cnt - 3}{2} \geq n - 1$ を変形して， $cnt \geq 2n + 1$ ． $P_1$ は"IOI"であることに注意．