結果

問題 No.866 レベルKの正方形
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:14:39
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,619 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 849,332 KB
最終ジャッジ日時 2025-06-12 16:14:45
合計ジャッジ時間 3,672 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 MLE * 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)]
    
    # 预处理每个字符的二维前缀和
    prefix = [[[0]*(W+1) for _ in range(H+1)] for _ in range(26)]
    for c_idx in range(26):
        c = chr(ord('a') + c_idx)
        for i in range(1, H+1):
            for j in range(1, W+1):
                current = 1 if grid[i-1][j-1] == c else 0
                prefix[c_idx][i][j] = prefix[c_idx][i-1][j] + prefix[c_idx][i][j-1] - prefix[c_idx][i-1][j-1] + current
    
    # 统计每个字符的总出现次数
    char_counts = [0] * 26
    for i in range(H):
        for j in range(W):
            c = grid[i][j]
            c_idx = ord(c) - ord('a')
            char_counts[c_idx] += 1
    
    # 按出现频率从高到低排序
    sorted_indices = sorted(range(26), key=lambda x: -char_counts[x])
    
    count = 0
    max_s = min(H, W)
    for s in range(1, max_s + 1):
        max_a = H - s + 1
        max_b = W - s + 1
        for a in range(1, max_a + 1):
            for b in range(1, max_b + 1):
                x2 = a + s - 1
                y2 = b + s - 1
                cnt = 0
                for c_idx in sorted_indices:
                    pre = prefix[c_idx]
                    total = pre[x2][y2] - pre[a-1][y2] - pre[x2][b-1] + pre[a-1][b-1]
                    if total > 0:
                        cnt += 1
                        if cnt > K:
                            break
                if cnt == K:
                    count += 1
    print(count)

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