結果

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

ソースコード

diff # 

import sys

def main():
    H, W, K = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(H)]
    ans = 0

    for s in range(1, min(H, W) + 1):
        if s > H or s > W:
            continue
        # Precompute the bitmask for each column's sliding window of s rows
        masks = [0] * W
        for j in range(W):
            mask = 0
            for i in range(s):
                mask |= 1 << (ord(grid[i][j]) - ord('a'))
            masks[j] = mask
        
        for i in range(H - s + 1):
            current_or = 0
            count = 0
            # Initialize the first s columns
            for j in range(s):
                current_or |= masks[j]
            if bin(current_or).count('1') == K:
                count += 1
            
            # Slide the window across columns
            for j in range(1, W - s + 1):
                # Remove the leftmost column
                left = j - 1
                # Add the new rightmost column
                right = j + s - 1
                # Recompute current_or as the OR of the s columns in the current window
                current_or = 0
                for k in range(j, j + s):
                    current_or |= masks[k]
                if bin(current_or).count('1') == K:
                    count += 1
            ans += count

            # Update masks for next row
            if i < H - s:
                for j in range(W):
                    # Remove the top character and add the new bottom character
                    top_char = grid[i][j]
                    bottom_char = grid[i + s][j]
                    if top_char == bottom_char:
                        continue  # Mask remains the same
                    # Recompute the mask for this column
                    new_mask = 0
                    for k in range(i + 1, i + 1 + s):
                        new_mask |= 1 << (ord(grid[k][j]) - ord('a'))
                    masks[j] = new_mask

    print(ans)

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