結果

問題 No.866 レベルKの正方形
ユーザー gew1fw
提出日時 2025-06-12 16:31:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,550 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 190,516 KB
最終ジャッジ日時 2025-06-12 16:32:24
合計ジャッジ時間 8,918 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    H, W, K = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(H)]
    grid = [[ord(c) - ord('a') for c in row] for row in grid]
    result = 0

    max_size = min(H, W)
    for size in range(1, max_size + 1):
        s = size - 1  # side length is size (s+1)
        if H - s < 1 or W - s < 1:
            continue
        # Precompute column counts for each column
        col_counts = [defaultdict(int) for _ in range(W)]
        # Initialize with the first 'size' rows
        for i in range(size):
            for b in range(W):
                c = grid[i][b]
                col_counts[b][c] += 1
        # Slide the row window
        for a in range(H - s):
            if a > 0:
                # Remove the previous top row (a-1)
                prev_row = a - 1
                for b in range(W):
                    c = grid[prev_row][b]
                    col_counts[b][c] -= 1
                    if col_counts[b][c] == 0:
                        del col_counts[b][c]
                # Add the new bottom row (a + s)
                new_row = a + s
                for b in range(W):
                    c = grid[new_row][b]
                    col_counts[b][c] += 1
            # Now process column window for current row window
            current = defaultdict(int)
            unique = 0
            # Initialize with first 'size' columns
            for b in range(size):
                for c, cnt in col_counts[b].items():
                    if cnt > 0:
                        if current[c] == 0:
                            unique += 1
                        current[c] += cnt
            if unique == K:
                result += 1
            # Slide the column window
            for b in range(1, W - s):
                # Remove the leftmost column (b-1)
                left = b - 1
                for c, cnt in col_counts[left].items():
                    if cnt > 0:
                        current[c] -= cnt
                        if current[c] == 0:
                            unique -= 1
                # Add the new right column (b + s)
                right = b + s
                for c, cnt in col_counts[right].items():
                    if cnt > 0:
                        if current[c] == 0:
                            unique += 1
                        current[c] += cnt
                if unique == K:
                    result += 1
    print(result)

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