結果

問題 No.2456 Stamp Art
ユーザー gew1fw
提出日時 2025-06-12 15:19:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,636 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 339,076 KB
最終ジャッジ日時 2025-06-12 15:19:11
合計ジャッジ時間 8,112 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    H, W = map(int, sys.stdin.readline().split())
    S = []
    for _ in range(H):
        line = sys.stdin.readline().strip()
        S.append(['.'] + list(line))
    S = [['.']*(W+1)] + S  # 1-based indexing

    # Precompute max_k: size of the largest square starting at (i,j) that is entirely black
    max_k = [[0]*(W+2) for _ in range(H+2)]
    for i in range(H, 0, -1):
        for j in range(W, 0, -1):
            if S[i][j] == '#':
                if i == H or j == W:
                    max_k[i][j] = 1
                else:
                    max_k[i][j] = 1 + min(max_k[i+1][j], max_k[i][j+1], max_k[i+1][j+1])
            else:
                max_k[i][j] = 0

    low = 1
    high = min(H, W)
    answer = 0

    def is_possible(k):
        if k == 0:
            return False

        row_max = [[0]*(W+1) for _ in range(H+1)]
        for i in range(1, H+1):
            dq = deque()
            for j in range(1, W+1):
                while dq and dq[0] < j - k + 1:
                    dq.popleft()
                while dq and max_k[i][dq[-1]] <= max_k[i][j]:
                    dq.pop()
                dq.append(j)
                if j >= k:
                    row_max[i][j] = max_k[i][dq[0]]
                else:
                    current_max = 0
                    for b in range(1, j+1):
                        if max_k[i][b] > current_max:
                            current_max = max_k[i][b]
                    row_max[i][j] = current_max

        col_max = [[0]*(W+1) for _ in range(H+1)]
        for j in range(1, W+1):
            dq = deque()
            for i in range(1, H+1):
                while dq and dq[0] < i - k + 1:
                    dq.popleft()
                while dq and row_max[dq[-1]][j] <= row_max[i][j]:
                    dq.pop()
                dq.append(i)
                if i >= k:
                    col_max[i][j] = row_max[dq[0]][j]
                else:
                    current_max = 0
                    for a in range(1, i+1):
                        if row_max[a][j] > current_max:
                            current_max = row_max[a][j]
                    col_max[i][j] = current_max

        for i in range(1, H+1):
            for j in range(1, W+1):
                if S[i][j] == '#' and col_max[i][j] < k:
                    return False
        return True

    while low <= high:
        mid = (low + high) // 2
        if is_possible(mid):
            answer = mid
            low = mid + 1
        else:
            high = mid - 1

    print(answer)

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