結果

問題 No.2456 Stamp Art
ユーザー gew1fw
提出日時 2025-06-12 12:52:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,813 ms / 5,000 ms
コード長 1,519 bytes
コンパイル時間 535 ms
コンパイル使用メモリ 82,788 KB
実行使用メモリ 324,880 KB
最終ジャッジ日時 2025-06-12 12:54:35
合計ジャッジ時間 33,615 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

H, W = map(int, input().split())
grid = [input().strip() for _ in range(H)]

prefix = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(1, H + 1):
    row_sum = 0
    for j in range(1, W + 1):
        row_sum += 1 if grid[i-1][j-1] == '#' else 0
        prefix[i][j] = prefix[i-1][j] + row_sum

def is_possible(k):
    if k == 0:
        return False
    diff = [[0] * (W + 2) for _ in range(H + 2)]
    max_a = H - k + 1
    max_b = W - k + 1
    for a in range(1, max_a + 1):
        a_end = a + k - 1
        for b in range(1, max_b + 1):
            b_end = b + k - 1
            total = prefix[a_end][b_end] - prefix[a-1][b_end] - prefix[a_end][b-1] + prefix[a-1][b-1]
            if total == k * k:
                diff[a][b] += 1
                diff[a][b_end + 1] -= 1
                diff[a_end + 1][b] -= 1
                diff[a_end + 1][b_end + 1] += 1

    # Compute row-wise prefix sums
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            diff[i][j] += diff[i][j-1]
    # Compute column-wise prefix sums
    for j in range(1, W + 1):
        for i in range(1, H + 1):
            diff[i][j] += diff[i-1][j]

    # Check all black cells
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#' and diff[i+1][j+1] == 0:
                return False
    return True

low = 1
high = min(H, W)
ans = 0
while low <= high:
    mid = (low + high) // 2
    if is_possible(mid):
        ans = mid
        low = mid + 1
    else:
        high = mid - 1
print(ans)
0