結果

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

ソースコード

diff # 

import sys

def main():
    H, W, K = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        line = sys.stdin.readline().strip()
        grid.append([ord(c) - ord('a') for c in line])
    
    result = 0
    max_size = min(H, W)
    
    for s in range(1, max_size + 1):
        if s > H or s > W:
            continue
        # For each column, maintain the count of each character in the current vertical window of size s
        vertical = [[0] * 26 for _ in range(W)]
        # Initialize vertical counts for the first s rows
        for j in range(W):
            for i in range(s):
                c = grid[i][j]
                vertical[j][c] += 1
        
        # Slide the vertical window from top to bottom
        for i in range(H - s + 1):
            # Now, slide horizontally
            total = [0] * 26
            unique = 0
            # Initialize the horizontal window with the first s columns
            for j in range(s):
                for c in range(26):
                    if vertical[j][c] > 0:
                        total[c] += vertical[j][c]
                        if total[c] == vertical[j][c]:
                            unique += 1
            if unique == K:
                result += 1
            
            # Slide the horizontal window to the right
            for j in range(1, W - s + 1):
                # Remove the leftmost column (j-1)
                left = j - 1
                for c in range(26):
                    if vertical[left][c] > 0:
                        total[c] -= vertical[left][c]
                        if total[c] == 0:
                            unique -= 1
                # Add the new rightmost column (j + s - 1)
                right = j + s - 1
                for c in range(26):
                    if vertical[right][c] > 0:
                        if total[c] == 0:
                            unique += 1
                        total[c] += vertical[right][c]
                if unique == K:
                    result += 1
            
            # Update vertical counts for next row (i+1)
            if i < H - s:
                for j in range(W):
                    # Remove the top character from the current vertical window
                    top_char = grid[i][j]
                    vertical[j][top_char] -= 1
                    # Add the new bottom character to the vertical window
                    bottom_char = grid[i + s][j]
                    vertical[j][bottom_char] += 1
    
    print(result)

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