結果

問題 No.3334 I hate Image Convolution
コンテスト
ユーザー kencho
提出日時 2025-11-23 01:39:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,237 bytes
コンパイル時間 324 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 149,524 KB
最終ジャッジ日時 2025-11-23 01:40:22
合計ジャッジ時間 24,543 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def solve():
    # 高速な入力読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    iterator = iter(input_data)
    
    try:
        num_test_cases = int(next(iterator))
    except StopIteration:
        return

    results = []

    for _ in range(num_test_cases):
        try:
            N = int(next(iterator))
            C_len = (N - 1) * (N - 1)
            C = []
            for _ in range(C_len):
                C.append(int(next(iterator)))
        except StopIteration:
            break

        # 戦略:
        # 1. Cを昇順にソートする。
        # 2. 行列Bを想定し、Bの値を列優先(Column-major)で埋めていく。
        #    つまり、B[0][0], B[1][0], ..., B[N-2][0], B[0][1], ... の順に小さい値を割り当てる。
        #    これにより、B[i][j]の値が前の列や上の行に比べて大きくなりやすくなり、
        #    非負制約を満たしやすくなる。
        
        C.sort()
        
        # Bの値を呼び出すためのイテレータ
        c_idx = 0
        
        # 行列Aの初期化 (N x N)
        # 最初は全て0とする。1列目(index 0)は0のまま固定する戦略をとる。
        A = [[0] * N for _ in range(N)]
        
        possible = True
        
        # Aの列 j (0-indexed) は固定済みとして、Bの列 j を満たすように Aの列 j+1 を計算する
        # Bの列 j は C から順番に取る
        
        for j in range(N - 1):
            # Aの列 j+1 を計算する
            # B[i][j] = A[i][j] + A[i+1][j] + A[i][j+1] + A[i+1][j+1]
            # 変形: A[i][j+1] + A[i+1][j+1] = B[i][j] - (A[i][j] + A[i+1][j])
            
            # A[0][j+1] = 0 と仮定して解き進める
            # これにより A[1][j+1], A[2][j+1]... が連鎖的に決まる
            
            curr_a_val = 0 # A[0][j+1]
            A[0][j+1] = curr_a_val
            
            for i in range(N - 1):
                # Bのこの位置に来るべき値（ソート済みリストから取得）
                b_val = C[c_idx]
                c_idx += 1
                
                # 直前の列からの寄与分
                prev_col_sum = A[i][j] + A[i+1][j]
                
                # 次の列（今求めている列）で必要な和
                target_sum = b_val - prev_col_sum
                
                # A[i][j+1] + A[i+1][j+1] = target_sum
                # A[i][j+1] (curr_a_val) は既知なので、A[i+1][j+1] を求める
                next_a_val = target_sum - curr_a_val
                
                if next_a_val < 0:
                    possible = False
                    break
                
                A[i+1][j+1] = next_a_val
                curr_a_val = next_a_val
            
            if not possible:
                break
        
        if possible:
            output_lines = []
            for row in A:
                output_lines.append(" ".join(map(str, row)))
            results.append("\n".join(output_lines))
        else:
            results.append("-1")

    print("\n".join(results))

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