結果

問題 No.866 レベルKの正方形
ユーザー lam6er
提出日時 2025-04-16 01:08:23
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,710 bytes
コンパイル時間 375 ms
コンパイル使用メモリ 81,260 KB
実行使用メモリ 848,208 KB
最終ジャッジ日時 2025-04-16 01:10:01
合計ジャッジ時間 3,127 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 MLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

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

    # Precompute prefix sums for each character
    prefix = [[[0]*(W+1) for _ in range(H+1)] for __ in range(26)]
    for c in range(26):
        char = chr(ord('a') + c)
        for i in range(1, H+1):
            row = grid[i-1]
            row_prefix = [0]*(W+1)
            for j in range(1, W+1):
                row_prefix[j] = row_prefix[j-1] + (1 if row[j-1] == char else 0)
                prefix[c][i][j] = prefix[c][i-1][j] + row_prefix[j]

    count = 0

    # Determine the minimum s such that s^2 >= K
    min_s = 1
    if K > 0:
        min_s = max(1, math.isqrt(K))
        if (min_s * min_s) < K:
            min_s += 1

    max_s = min(H, W)
    for s in range(min_s, max_s + 1):
        s_size = s
        max_i = H - s_size + 1
        max_j = W - s_size + 1
        if max_i < 1 or max_j < 1:
            continue
        for i in range(1, max_i + 1):
            a = i
            c = i + s_size - 1
            for j in range(1, max_j + 1):
                b = j
                d = j + s_size - 1
                unique = 0
                for char_idx in range(26):
                    # Calculate the sum for this character in the square
                    total = prefix[char_idx][c][d] - prefix[char_idx][a-1][d] - prefix[char_idx][c][b-1] + prefix[char_idx][a-1][b-1]
                    if total > 0:
                        unique += 1
                        if unique > K:
                            break
                if unique == K:
                    count += 1
    print(count)

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