ABC337 D - Cheating Gomoku Narabe - 黒ココアさんのメモ置き場

問題

グリッドが与えられるよ
- それぞれのマスには、o,x,.のどれかが書いてあるよ
好きな数だけ、.をoに変えることができるよ(操作)
縦横（斜め無し）でoが$K$個続くような盤面作りたいよ
- そんな盤面作れる？作れるなら、最小操作数教えてね

成約

$ H \times W \leq 2 \times 10^5$

思考

全マス見ていくのは可能な規模感
とりあえずxは操作できないので….とoの連続部分で、勝負したいね
一旦横で勝利条件が満たせるかを確認
- 縦の方向は、盤面90度回転して再度横向きに見れば良いので
じゃあ、1行手にとって。
- xを挟むとダメなので、まずはxで分割してあげて
  - 一欠片の長さが$K$未満なら、作れないから捨て
  - 長さが$K$以上なら、そこで勝利条件満たせるね！
    - 後は、その欠片のうちどこで満たせば操作回数少ないかなぁ、を横から見ていく話
    - 累積和でも良さそう？
    - 今回は尺取り法的に処理しました！（どうせ使い回さないので）
      - 2次元累積和を前処理で作ってたら、回転に合わせて使いまわせてたのかな

コード

from collections import deque

H,W,K = map(int,input().split())
grid_L = []
for i in range(H):
    grid_L.append(input())

def check(s):
    que = deque()
    score = 0
    ret = 10**18
    for i in range(len(s)):
        que.append(s[i])
        if s[i] == ".":
            score += 1
        while len(que) > K:
            if que.popleft() == ".":
                score -= 1
        if len(que) == K:
            ret = min(ret,score)
    return ret

ans = 10**18

for row in grid_L:
    for parts in row.split("x"):
        if len(parts) < K:continue
        ans = min(ans,check(parts))

grid_L = list(zip(*reversed(grid_L)))

for row in grid_L:
    row = "".join(row)
    for parts in row.split("x"):
        if len(parts) < K:continue
        ans = min(ans,check(parts))

if ans == 10**18:
    print(-1)
else:
    print(ans)