結果

問題 No.3813 Ashwreath
コンテスト
ユーザー sepa38
提出日時 2026-11-18 15:16:40
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 3,913 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 96 ms
コンパイル使用メモリ 64,424 KB
実行使用メモリ 59,648 KB
最終ジャッジ日時 2026-11-20 20:54:00
合計ジャッジ時間 3,245 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

# 誤解法: 最終行の良いマスの条件チェック漏れ
import sys


def solve(N, M, S):
    fire = [[S[i][j] == '#' for j in range(M)] for i in range(N)]

    def fire_cnt(i, j):
        c = 0
        for di in (-1, 0, 1):
            for dj in (-1, 0, 1):
                if di == 0 and dj == 0:
                    continue
                a, b = i + di, j + dj
                if 0 <= a < N and 0 <= b < M and fire[a][b]:
                    c += 1
        return c

    # 良いマスになり得る候補 = 空きマス かつ 火の隣接が 2 個以上
    cand = [[(not fire[i][j]) and fire_cnt(i, j) >= 2 for j in range(M)] for i in range(N)]

    # 各マスの状態(植えない空きマスは「植える」に置き換えても損しない)
    #   0: 植物なし・要求なし(火 or 条件達成済みの良いマス)
    #   1: 植物あり
    #   2: 良いマス(あと 1 個植物が必要)
    #   3: 良いマス(あと 2 個植物が必要)
    # プロファイル: 直近 M+1 マス(行優先)の状態。
    # state[k] = k マス前に決めたマスの状態 (k=1..M+1) を 2bit ずつ詰める。
    W = M + 1
    mask_all = (1 << (2 * W)) - 1

    def get(st, k):  # k マス前 (1-indexed)
        return (st >> (2 * (k - 1))) & 3

    dp = {0: 0}  # 盤面の外は状態 0(植物なし・要求なし)扱い
    for i in range(N):
        for j in range(M):
            # 既に決まっている隣接マス: 左 (k=1), 左上 (k=M+1), 上 (k=M), 右上 (k=M-1)
            nbrs = []
            if j > 0:
                nbrs.append(1)
            if i > 0:
                nbrs.append(M)
                if j > 0:
                    nbrs.append(M + 1)
                if j < M - 1:
                    nbrs.append(M - 1)
            if fire[i][j]:
                opts = (0,)
            elif cand[i][j]:
                opts = (1, 3)
            else:
                opts = (1,)
            ndp = {}
            for st, val in dp.items():
                for o in opts:
                    s = st
                    cur = o
                    ok = True
                    if o == 1:
                        # 植えたので、隣接の良いマスの要求を減らす
                        for k in nbrs:
                            v = get(s, k)
                            if v >= 2:
                                nv = 0 if v == 2 else 2
                                s ^= (v ^ nv) << (2 * (k - 1))
                    elif o == 3:
                        need = 2
                        for k in nbrs:
                            if get(s, k) == 1:
                                need -= 1
                        cur = (0, 2, 3)[max(need, 0)]
                    # M+1 マス前 (= 左上) はこれで隣接 8 マスが全部確定 → 検証して捨てる
                    if i > 0 and j > 0:
                        if get(s, M + 1) >= 2:
                            ok = False
                    if not ok:
                        continue
                    ns = ((s << 2) | cur) & mask_all
                    nv = val + (1 if o == 3 else 0)
                    if ndp.get(ns, -1) < nv:
                        ndp[ns] = nv
            dp = ndp
        # 行末: 1 つ上の行の最後のマス (i-1, M-1) は今の行の (i, M-1) で
        # 隣接が全確定しているので、ここで検証する(k = M+1 にいる)
        if i > 0:
            dp = {st: v for st, v in dp.items() if get(st, M + 1) < 2}
    # 最終行の良いマスは下側が存在しないので、要求が残っていないかを確認
    best = 0
    for st, v in dp.items():
        if True:
            best = max(best, v)
    return best


def main():
    data = sys.stdin.read().split()
    N, M = int(data[0]), int(data[1])
    S = data[2:2 + N]
    print(solve(N, M, S))


if __name__ == "__main__":
    main()
0