結果

問題 No.2178 Payable Magic Items
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:05:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,999 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 282,300 KB
最終ジャッジ日時 2025-04-15 23:07:45
合計ジャッジ時間 20,584 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import product

def main():
    N, K = map(int, sys.stdin.readline().split())
    input_points = []
    for _ in range(N):
        s = sys.stdin.readline().strip()
        point = tuple(int(c) for c in s)
        input_points.append(point)
    
    # Initialize frequency and suffix_sum dictionaries
    freq = {}
    suffix_sum = {}
    for p in input_points:
        freq[p] = 1
        suffix_sum[p] = 1
    
    # Process each dimension in reverse order
    for d in reversed(range(K)):
        other_dims = [i for i in range(K) if i != d]
        # Generate all possible combinations of the other K-1 dimensions
        for other_values in product(range(5), repeat=K-1):
            # Process current dimension's values from 4 down to 0
            for d_val in range(4, -1, -1):
                # Build the current point's coordinates
                coords = [0] * K
                idx = 0
                for dim in range(K):
                    if dim == d:
                        coords[dim] = d_val
                    else:
                        coords[dim] = other_values[idx]
                        idx += 1
                current_point = tuple(coords)
                # Compute next_val in this dimension
                next_val = d_val + 1
                if next_val > 4:
                    continue
                next_coords = list(coords)
                next_coords[d] = next_val
                next_point = tuple(next_coords)
                # Update suffix_sum for current_point
                # Use get to handle missing keys with default 0
                current_sum = suffix_sum.get(current_point, 0)
                next_sum = suffix_sum.get(next_point, 0)
                suffix_sum[current_point] = current_sum + next_sum
    
    # Calculate the answer
    answer = 0
    for p in input_points:
        cnt = suffix_sum.get(p, 0)
        if cnt >= 2:
            answer += 1
    print(answer)

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