結果
| 問題 | No.3506 All Distance is Square Number |
| コンテスト | |
| ユーザー |
 はじっこゆーれー
|
| 提出日時 | 2026-04-18 02:51:55 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,866 bytes |
| 記録 | |
| コンパイル時間 | 405 ms |
| コンパイル使用メモリ | 85,120 KB |
| 実行使用メモリ | 325,120 KB |
| 最終ジャッジ日時 | 2026-04-18 02:52:11 |
| 合計ジャッジ時間 | 6,867 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 RE * 26 |
ソースコード
import sys
def solve():
sys.setrecursionlimit(2000)
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
is_sq = [False] * 40001
for i in range(1, 201):
is_sq[i * i] = True
E = [0] * (N + 1)
P = [0] * (N + 1)
pref = [0] * (N + 1)
used = [False] * 201
active_paths = [set() for _ in range(N + 1)]
def dfs(k):
if k == N + 1:
return True
for p in range(1, 201):
if used[p]: continue
satisfied_without_E = [False] * k
for i in range(1, k):
for val in active_paths[i]:
if is_sq[val + p]:
satisfied_without_E[i] = True
break
valid_E = set()
for e in range(1, 201):
if not used[e] and e != p:
valid_E.add(e)
possible = True
for i in range(1, k):
if satisfied_without_E[i]: continue
temp_valid = set()
if i == 1:
for e in valid_E:
if is_sq[e]:
temp_valid.add(e)
else:
for e in valid_E:
good_e = False
for x in range(2, k):
dist = abs(pref[i] - pref[x]) + E[x] + e
if is_sq[dist]:
good_e = True
break
if good_e:
temp_valid.add(e)
valid_E = temp_valid
if not valid_E:
possible = False
break
if possible:
for e in valid_E:
used[p] = True
used[e] = True
P[k] = p
E[k] = e
pref[k] = pref[k-1] + p
old_active = [active_paths[i].copy() for i in range(1, k+1)]
for i in range(1, k):
active_paths[i] = {val + p for val in active_paths[i]}
active_paths[1].add(e)
for i in range(2, k):
for x in range(2, k):
dist = abs(pref[i] - pref[x]) + E[x] + e
active_paths[i].add(dist)
active_paths[k].add(0)
if dfs(k + 1):
return True
used[p] = False
used[e] = False
for i in range(1, k+1):
active_paths[i] = old_active[i]
return False
for e2 in range(1, 201):
if is_sq[e2]:
E[2] = e2
used[e2] = True
active_paths[1].add(e2)
active_paths[2].add(0)
pref[2] = 0
if dfs(3):
break
used[e2] = False
active_paths[1].clear()
active_paths[2].clear()
print(2 * N - 3)
E_idx = {}
P_idx = {}
edge_count = 1
for k in range(2, N + 1):
E_idx[k] = edge_count
print(f"1 {k} {E[k]}")
edge_count += 1
for k in range(3, N + 1):
P_idx[k] = edge_count
print(f"{k - 1} {k} {P[k]}")
edge_count += 1
for i in range(1, N):
for j in range(i + 1, N + 1):
path = None
if is_sq[pref[j] - pref[i]]:
path = [P_idx[m] for m in range(i+1, j+1)]
if path is None:
if i == 1:
if is_sq[E[j]]:
path = [E_idx[j]]
else:
for x in range(2, j):
if is_sq[E[x] + pref[j] - pref[x]]:
path = [E_idx[x]] + [P_idx[m] for m in range(x+1, j+1)]
break
else:
for x in range(2, j):
dist_x_i = abs(pref[i] - pref[x])
if is_sq[dist_x_i + E[x] + E[j]]:
path = []
if x <= i:
path.extend([P_idx[m] for m in range(i, x, -1)])
else:
path.extend([P_idx[m] for m in range(i+1, x+1)])
path.extend([E_idx[x], E_idx[j]])
break
if path is None:
for y in range(i+1, j):
for x in range(2, y):
dist_x_i = abs(pref[i] - pref[x])
if is_sq[dist_x_i + E[x] + E[y] + pref[j] - pref[y]]:
path = []
if x <= i:
path.extend([P_idx[m] for m in range(i, x, -1)])
else:
path.extend([P_idx[m] for m in range(i+1, x+1)])
path.extend([E_idx[x], E_idx[y]])
path.extend([P_idx[m] for m in range(y+1, j+1)])
break
if path is not None:
break
print(f"{len(path)} {' '.join(map(str, path))}")
solve()