結果

問題 No.866 レベルKの正方形
ユーザー lam6er
提出日時 2025-03-31 17:46:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,540 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 76,988 KB
最終ジャッジ日時 2025-03-31 17:47:28
合計ジャッジ時間 9,090 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left, bisect_right

def main():
    H, W, K = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(H)]
    
    # Preprocess: for each column j, record the positions of each character
    cols = []
    for j in range(W):
        pos_dict = {}
        for i in range(H):
            c = grid[i][j]
            if c not in pos_dict:
                pos_dict[c] = []
            pos_dict[c].append(i + 1)  # Using 1-based indexing
        cols.append(pos_dict)
    
    res = 0
    max_size = min(H, W)
    for s in range(1, max_size + 1):
        max_i = H - s + 1
        if max_i < 1:
            continue
        for i in range(1, max_i + 1):
            i_end = i + s - 1
            valid = 0
            # Precompute bitmask for each column
            bitmasks = []
            for j in range(W):
                current_bm = 0
                pos_dict = cols[j]
                for c in pos_dict:
                    positions = pos_dict[c]
                    left = bisect_left(positions, i)
                    right_idx = bisect_right(positions, i_end)
                    if left < right_idx:
                        char_idx = ord(c) - ord('a')
                        current_bm |= 1 << char_idx
                bitmasks.append(current_bm)
            
            # Sliding window on columns with bitmasks
            current_counts = [0] * 26
            unique_chars = 0
            left = 0
            for right in range(W):
                # Add bitmask at 'right' to current window
                bm = bitmasks[right]
                for idx in range(26):
                    if (bm >> idx) & 1:
                        if current_counts[idx] == 0:
                            unique_chars += 1
                        current_counts[idx] += 1
                # Maintain window size == s
                while right - left + 1 > s:
                    # Remove bitmask at 'left'
                    bm_left = bitmasks[left]
                    for idx in range(26):
                        if (bm_left >> idx) & 1:
                            current_counts[idx] -= 1
                            if current_counts[idx] == 0:
                                unique_chars -= 1
                    left += 1
                # Check if window size is exactly s and count
                if right - left + 1 == s and unique_chars == K:
                    valid += 1
            res += valid
    print(res)

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