結果
| 問題 | No.3334 I hate Image Convolution |
| コンテスト | |
| ユーザー |
 kencho
|
| 提出日時 | 2025-11-23 01:46:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 394 ms / 3,000 ms |
| コード長 | 5,853 bytes |
| コンパイル時間 | 562 ms |
| コンパイル使用メモリ | 82,572 KB |
| 実行使用メモリ | 151,696 KB |
| 最終ジャッジ日時 | 2025-11-23 01:47:19 |
| 合計ジャッジ時間 | 27,043 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 56 |
ソースコード
import sys
from collections import deque
# 再帰上限を増やす（念のため）
sys.setrecursionlimit(2000)
def solve():
# 高速な入力読み込み
input_data = sys.stdin.read().split()
if not input_data:
return
iterator = iter(input_data)
try:
num_test_cases_str = next(iterator, None)
if num_test_cases_str is None:
return
num_test_cases = int(num_test_cases_str)
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を昇順ソートしてBを構成
C.sort()
# Aの初期構築（負の値を許容）
# A[i][0] = 0, A[0][j] = 0 として残りを計算
A = [[0] * N for _ in range(N)]
# Bを列優先で埋めていくと仮定して計算
# B[i][j]に対応するCの値
c_idx = 0
# 列ごとに計算
for j in range(N - 1):
# A[0][j+1] = 0 (固定)
curr_a_val = 0
A[0][j+1] = 0
for i in range(N - 1):
b_val = C[c_idx]
c_idx += 1
# A[i+1][j+1] = B[i][j] - A[i][j] - A[i+1][j] - A[i][j+1]
val = b_val - A[i][j] - A[i+1][j] - curr_a_val
A[i+1][j+1] = val
curr_a_val = val
# 2. 差分制約システムの構築
# A'[i][j] = A[i][j] + (-1)^i * x[j] + (-1)^j * y[i] >= 0
# 変数変換を行い、差分制約 Y[i] - X[j] <= W の形にする
# ノード: 0~(N-1) が X (列に対応), N~(2N-1) が Y (行に対応)
# パリティによる変換定義:
# X[j] = x[j] (j偶数), -x[j] (j奇数)
# Y[i] = -y[i] (i偶数), y[i] (i奇数)
# とすると、全ての制約が Y'[i] - X'[j] <= A[i][j] の形に統一される（Y', X'は符号調整後の変数）
# 具体的には:
# i%2 == j%2 (同パリティ): Y[i] - X[j] <= A[i][j]
# i%2 != j%2 (異パリティ): X[j] - Y[i] <= A[i][j]
# グラフ構築
adj = [[] for _ in range(2 * N)]
# 行列全体を走査してエッジを追加
for r in range(N):
for c in range(N):
w = A[r][c]
u_x = c # X_c ノード番号
v_y = N + r # Y_r ノード番号
if (r % 2) == (c % 2):
# Y[r] - X[c] <= A[r][c] => X[c] --(w)--> Y[r]
adj[u_x].append((v_y, w))
else:
# X[c] - Y[r] <= A[r][c] => Y[r] --(w)--> X[c]
adj[v_y].append((u_x, w))
# 3. SPFA (Shortest Path Faster Algorithm) で最短路（ポテンシャル）を求める
# 始点0から全ノードへの最短距離を求める
# グラフが非連結の可能性があるので、全ノードをキューに入れて距離0で初期化するのと同義
dist = [0] * (2 * N)
count = [0] * (2 * N)
in_queue = [True] * (2 * N)
queue = deque(range(2 * N))
possible = True
while queue:
u = queue.popleft()
in_queue[u] = False
for v, weight in adj[u]:
if dist[v] > dist[u] + weight:
dist[v] = dist[u] + weight
count[v] += 1
if count[v] > 2 * N: # 負閉路検出（念のため）
possible = False
break
if not in_queue[v]:
queue.append(v)
in_queue[v] = True
if not possible:
break
if not possible:
results.append("-1")
continue
# 4. 解の復元
# SPFAの結果 dist[] がポテンシャル
# X'[j] = dist[j], Y'[i] = dist[N+i]
# 元の x, y への変換と A の更新
# パリティ定義:
# X'[j] = x[j] (j偶数), -x[j] (j奇数) => x[j] = X'[j] if even else -X'[j]
# Y'[i] = -y[i] (i偶数), y[i] (i奇数) => y[i] = -Y'[i] if even else Y'[i]
# 更新式: A'[i][j] = A[i][j] + (-1)^i * x[j] + (-1)^j * y[i]
X_prime = dist[:N]
Y_prime = dist[N:]
ans_A = []
for r in range(N):
row_vals = []
# y[r] の計算
if r % 2 == 0:
y_r = -Y_prime[r]
else:
y_r = Y_prime[r]
term_y = y_r * (1 if r % 2 == 0 else -1) # (-1)^j * y[i] の係数は j 依存だが、ここでは (-1)^r * (-1)^r * y[i]??
# 整理:
# term_i = (-1)^i * x[j]
# term_j = (-1)^j * y[i]
for c in range(N):
# x[c] の計算
if c % 2 == 0:
x_c = X_prime[c]
else:
x_c = -X_prime[c]
term_x = x_c if r % 2 == 0 else -x_c # (-1)^i * x[j]
term_y_val = y_r if c % 2 == 0 else -y_r # (-1)^j * y[i]
val = A[r][c] + term_x + term_y_val
row_vals.append(str(val))
ans_A.append(" ".join(row_vals))
results.append("\n".join(ans_A))
print("\n".join(results))
if __name__ == "__main__":
solve()