結果
| 問題 | No.3813 Ashwreath |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-18 15:13:17 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 3,949 bytes |
| 記録 | |
| コンパイル時間 | 115 ms |
| コンパイル使用メモリ | 64,052 KB |
| 実行使用メモリ | 62,244 KB |
| 最終ジャッジ日時 | 2026-11-20 20:53:54 |
| 合計ジャッジ時間 | 3,793 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 WA * 7 |
ソースコード
# 誤解法: 火の隣接条件を「1 個以上」と誤読
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) >= 1 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 all(get(st, k) < 2 for k in range(1, M + 1)):
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()
sepa38