結果

問題 No.2456 Stamp Art
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 12:53:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,942 bytes
コンパイル時間 440 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 286,640 KB
最終ジャッジ日時 2025-06-12 12:55:34
合計ジャッジ時間 7,971 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(H)]
    
    # Precompute the 2D prefix sum
    prefix = [[0]*(W+1) for _ in range(H+1)]
    for i in range(H):
        row_sum = 0
        for j in range(W):
            row_sum += 1 if grid[i][j] == '#' else 0
            prefix[i+1][j+1] = prefix[i][j+1] + row_sum
    
    max_k = min(H, W)
    for k in range(max_k, 0, -1):
        if k == 1:
            print(1)
            return
        valid_squares = []
        for a in range(H - k + 1):
            for b in range(W - k + 1):
                total = prefix[a + k][b + k] - prefix[a][b + k] - prefix[a + k][b] + prefix[a][b]
                if total == k * k:
                    valid_squares.append((a, b))
        if not valid_squares:
            continue
        
        row_intervals = [[] for _ in range(H)]
        for a, b in valid_squares:
            start_row = a
            end_row = a + k - 1
            start_col = b
            end_col = b + k - 1
            for i in range(start_row, end_row + 1):
                if i >= H:
                    continue
                row_intervals[i].append((start_col, end_col))
        
        merged = []
        for i in range(H):
            intervals = row_intervals[i]
            if not intervals:
                merged.append([])
                continue
            intervals.sort()
            merged_intervals = []
            current_start, current_end = intervals[0]
            for s, e in intervals[1:]:
                if s <= current_end + 1:
                    current_end = max(current_end, e)
                else:
                    merged_intervals.append((current_start, current_end))
                    current_start, current_end = s, e
            merged_intervals.append((current_start, current_end))
            merged.append(merged_intervals)
        
        all_covered = True
        for i in range(H):
            for j in range(W):
                if grid[i][j] == '#':
                    if not merged[i]:
                        all_covered = False
                        break
                    left, right = 0, len(merged[i]) - 1
                    found = False
                    while left <= right:
                        mid = (left + right) // 2
                        s, e = merged[i][mid]
                        if s <= j <= e:
                            found = True
                            break
                        elif j < s:
                            right = mid - 1
                        else:
                            left = mid + 1
                    if not found:
                        all_covered = False
                        break
            if not all_covered:
                break
        if all_covered:
            print(k)
            return
    print(1)

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