結果

問題 No.2456 Stamp Art
ユーザー lam6er
提出日時 2025-04-16 15:47:50
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,747 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,028 KB
実行使用メモリ 848,756 KB
最終ジャッジ日時 2025-04-16 15:48:45
合計ジャッジ時間 4,536 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        line = sys.stdin.readline().strip()
        grid.append(line)
    
    # Convert grid to binary matrix (1 for black)
    bin_grid = [ [0]*(W+2) for _ in range(H+2) ]
    black_cells = []
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                bin_grid[i+1][j+1] = 1
                black_cells.append( (i+1, j+1) )
    
    # Compute DP array where DP[i][j] is the largest square starting at (i,j)
    DP = [ [0]*(W+2) for _ in range(H+2) ]
    for i in range(H, 0, -1):
        for j in range(W, 0, -1):
            if bin_grid[i][j] == 0:
                DP[i][j] = 0
            else:
                if i == H or j == W:
                    DP[i][j] = 1
                else:
                    DP[i][j] = 1 + min(DP[i+1][j], DP[i][j+1], DP[i+1][j+1])
    
    # Precompute log values for rows and columns
    max_log_row = 0 if H == 0 else math.floor(math.log2(H))
    max_log_col = 0 if W == 0 else math.floor(math.log2(W))
    
    log_row = [0] * (H + 1)
    for i in range(2, H + 1):
        log_row[i] = log_row[i // 2] + 1
    
    log_col = [0] * (W + 1)
    for j in range(2, W + 1):
        log_col[j] = log_col[j // 2] + 1
    
    # Build sparse table for 2D range maximum query
    st = [[[[0] * (W + 2) for _ in range(H + 2)] for __ in range(max_log_col + 1)] for ___ in range(max_log_row + 1)]
    
    # Base case: kr=0, kc=0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            st[0][0][i][j] = DP[i][j]
    
    # Build for kr > 0
    for kr in range(1, max_log_row + 1):
        step = 1 << (kr - 1)
        for i in range(1, H - (1 << kr) + 2):
            for j in range(1, W + 1):
                st[kr][0][i][j] = max(st[kr-1][0][i][j], st[kr-1][0][i + step][j])
    
    # Build for kc > 0
    for kc in range(1, max_log_col + 1):
        step = 1 << (kc - 1)
        for kr in range(max_log_row + 1):
            row_step = 1 << kr
            for i in range(1, H - row_step + 2):
                for j in range(1, W - (1 << kc) + 2):
                    st[kr][kc][i][j] = max(st[kr][kc-1][i][j], st[kr][kc-1][i][j + step])
    
    def query_max(a, x, b, y):
        if a > x or b > y:
            return 0
        len_rows = x - a + 1
        len_cols = y - b + 1
        kr = log_row[len_rows] if len_rows > 0 else 0
        kc = log_col[len_cols] if len_cols > 0 else 0
        step_r = 1 << kr
        step_c = 1 << kc
        
        max_val = 0
        if a <= x and b <= y:
            max_val = max(max_val, st[kr][kc][a][b])
        if a <= x and (y - step_c + 1) >= b:
            max_val = max(max_val, st[kr][kc][a][y - step_c + 1])
        if (x - step_r + 1) >= a and b <= y:
            max_val = max(max_val, st[kr][kc][x - step_r + 1][b])
        if (x - step_r + 1) >= a and (y - step_c + 1) >= b:
            max_val = max(max_val, st[kr][kc][x - step_r + 1][y - step_c + 1])
        return max_val
    
    # Binary search for the maximum k
    low = 1
    high = min(H, W)
    ans = 1
    while low <= high:
        mid = (low + high) // 2
        valid = True
        for (x, y) in black_cells:
            a = max(1, x - mid + 1)
            x_end = x
            b = max(1, y - mid + 1)
            y_end = y
            if a > x_end or b > y_end:
                valid = False
                break
            max_dp = query_max(a, x_end, b, y_end)
            if max_dp < mid:
                valid = False
                break
        if valid:
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    print(ans)

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