ARC007 C - 節約生活

問題原文

atcoder.jp

解法

sample2で貪欲の線はなくなる。

制約が小さいので「どこからテレビをつけ始めるか」のbit全探索ができる。

実装

過去にテレビを点けといたことにして、今から 分間ついてればOKみたいな感じにした。
modでやればよかったと後悔（まぁいいか）

from itertools import product
S = list(input())
N = len(S)

ans = float('inf')
for pattern in product([0, 1], repeat=N):
    pattern = list(pattern)
    X = [0] * (2 * N)
    for i, p in enumerate(pattern):
        if p == 0:
            continue
        for j, s in enumerate(S, start=i):
            if s == 'x':
                continue
            X[j] = 1
            if j + N < 2 * N:
                X[j + N] = 1
    if sum(X[N:]) == N:
        ans = min(ans, sum(pattern))

print(ans)

感想

推定diff1400ぐらいらしい。こういう実装問題は普通にすき。
令和ABCなら800はつきそうだなぁ。