Pythonで理解する蟻本「3-2 Face The Right Way（POJ No.3276）」(p.139)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「3-2 Face The Right Way（POJ No.3276）」(p.139)
のコードをPythonで書き直したものとなっています。

入力

入力例

7
BBFBFBB

解答

MAX_N = 5000

# 入力
N = int(input())
DIR = [c == 'B' for c in input()]    # 牛の方向(0:F, 1:B)


# Kを固定したときの最小操作回数を求める
# 解が存在しないならば-1
def calc(K):
    f = [0] * MAX_N    # 区間[i,i+K-1]を反転させたかどうか
    res = 0
    SUM = 0    # fの和
    for i in range(N - K + 1):
        # 区間[i,i+K-1]に着目
        if (DIR[i] + SUM) % 2 != 0:
            # 先頭の牛が後ろを向いている
            res += 1
            f[i] = 1
        SUM += f[i]
        if i - K + 1 >= 0:
            SUM -= f[i - K + 1]
    
    # 残りの牛が前を向いているかをチェック
    for i in range(N - K + 1, N):
        if (DIR[i] + SUM) % 2 != 0:
            # 解なし
            return -1
        if i - K + 1 >= 0:
            SUM -= f[i - K + 1]
    return res

K = 1
M = N
for k in range(1, N + 1):
    m = calc(k)
    if m >= 0 and M > m:
        M = m
        K = k
print(K, M)