結果
| 問題 | No.3506 All Distance is Square Number |
| コンテスト | |
| ユーザー |
 edon8618
|
| 提出日時 | 2026-04-20 14:50:36 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,708 bytes |
| 記録 | |
| コンパイル時間 | 134 ms |
| コンパイル使用メモリ | 85,120 KB |
| 実行使用メモリ | 96,896 KB |
| 最終ジャッジ日時 | 2026-04-20 14:50:45 |
| 合計ジャッジ時間 | 7,099 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 RE * 28 |
ソースコード
import sys
import random
def solve():
# 入力を受け取る (N)
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
if N == 2:
# N=2 の自明なケース
print(1) # 辺数 M
print("1 2 1") # u v w
print("1 1") # length_of_path, edge_id
return
# 重みの候補 (1〜200)
U = list(range(1, 201))
# 辺リスト: (u, v, w, id)
edges = []
# DP用のマスク配列: masks[a][b] に a と b の間の単純パスの長さ(の集合)をビットで持つ
# a > b となるようにアクセスする
masks = [[0] * (N + 1) for _ in range(N + 1)]
# 平方数のビットマスク (最悪パス長は 200 * 100 = 20000 なので 150^2=22500 まであれば十分)
SQUARES_MASK = 0
for i in range(1, 151):
SQUARES_MASK |= (1 << (i * i))
# 初期状態 (頂点1と2)
U.remove(1)
edges.append((1, 2, 1, 1))
masks[2][1] = (1 << 1)
masks[1][1] = 1
masks[2][2] = 1
edge_id_counter = 2
vertex_info = [None] * (N + 1)
# 乱数シード固定で決定的にする（ジャッジ側での実行の一貫性を担保）
rng = random.Random(42)
for i in range(3, N + 1):
# 利用可能な重みのペアを総和が小さい順に試す (パス長が爆発して平方数の上限を超えないようにする)
U_pairs = []
for xi in range(len(U)):
for yi in range(xi + 1, len(U)):
U_pairs.append((U[xi], U[yi], xi, yi))
U_pairs.sort(key=lambda item: item[0] + item[1])
# 接続先候補 (u, v) をランダムに並べる（特定の部分木に偏るのを防ぐ）
candidates_uv = []
for u in range(1, i):
for v in range(1, i):
if u != v:
candidates_uv.append((u, v))
rng.shuffle(candidates_uv)
found = False
best_u = best_v = best_x = best_y = idx_x = idx_y = -1
for x, y, xi, yi in U_pairs:
if found: break
for u, v in candidates_uv:
ok = True
# i番目の頂点を追加したとき、すべての k < i について平方数パスが1つ以上作れるか判定
for k in range(1, i):
mask_u = masks[max(u, k)][min(u, k)]
mask_v = masks[max(v, k)][min(v, k)]
new_mask = (mask_u << x) | (mask_v << y)
if (new_mask & SQUARES_MASK) == 0:
ok = False
break
if ok:
found = True
best_u, best_v, best_x, best_y = u, v, x, y
idx_x, idx_y = xi, yi
break
if not found:
raise Exception(f"Failed to find valid connection for vertex {i}")
ex = edge_id_counter
ey = edge_id_counter + 1
edge_id_counter += 2
vertex_info[i] = (best_u, best_v, best_x, best_y, ex, ey)
edges.append((i, best_u, best_x, ex))
edges.append((i, best_v, best_y, ey))
# 使った重みをリストから削除 (インデックスがズレないよう大きい方からpop)
U.pop(max(idx_x, idx_y))
U.pop(min(idx_x, idx_y))
# 決定した状態をもとにマスクを確定
masks[i][i] = 1
for k in range(1, i):
mask_u = masks[max(best_u, k)][min(best_u, k)]
mask_v = masks[max(best_v, k)][min(best_v, k)]
masks[i][k] = (mask_u << best_x) | (mask_v << best_y)
def get_path(a, b):
""" a から b (a > b) への条件を満たす単純パスを復元する """
valid_sq = masks[a][b] & SQUARES_MASK
if valid_sq == 0:
raise Exception("No path found!")
# 存在する平方数パスのうち最小の長さを採用
L = (valid_sq & -valid_sq).bit_length() - 1
path = []
curr_max = a
curr_min = b
while curr_max != curr_min:
u, v, x, y, ex, ey = vertex_info[curr_max]
# u 側から来たルートか検証
next_max_u, next_min_u = max(u, curr_min), min(u, curr_min)
if L >= x and (masks[next_max_u][next_min_u] & (1 << (L - x))):
path.append(ex)
L -= x
curr_max, curr_min = next_max_u, next_min_u
continue
# v 側から来たルートか検証
next_max_v, next_min_v = max(v, curr_min), min(v, curr_min)
if L >= y and (masks[next_max_v][next_min_v] & (1 << (L - y))):
path.append(ey)
L -= y
curr_max, curr_min = next_max_v, next_min_v
continue
raise Exception("Traceback failed!")
return path
# === 出力パート ===
M = len(edges)
# グラフの出力 (フォーマットの仕様に合わせてここは適宜調整してください)
print(f"{M}")
for u, v, w, eid in edges:
print(f"{u} {v} {w}")
# パスの出力 (1 <= i < j <= N)
for i in range(1, N):
for j in range(i + 1, N + 1):
p = get_path(j, i)
p.reverse() # i から j への向かう順番にするため反転
# len(Q) e_1 e_2 ... の形式で出力
print(f"{len(p)} " + " ".join(map(str, p)))
if __name__ == '__main__':
solve()