問題の解説

早速ですが、まずは解法を説明します。

\((p_i, p_j)\) が全体で \(r_{i, j}\) 番目に 遠い 点対であるとします（つまり \(r_{A_i, B_i} = \frac{N(N-1)}{2} - i + 1\)）。このとき、以下の点の配置が条件を満たします。

\[ \begin{aligned} p_1 & = (L, r_{1, 2}, \dots, r_{1, N}) \\ p_2 & = (0, L, \dots, r_{2, N}) \\ & \vdots \\ p_N & = (0, 0, \dots, L) \end{aligned} \]

ただし、\(L\) は十分大きい定数とします。本問題の制約下では、\(L = 10^8\) で十分です。

---

どうやって解法を思いつくか？

解法を聞くと「天才的なひらめきだ！」と思うかもしれませんが、自然な考え方を踏んでその解法にたどり着くことは可能です。

ここからは、正解に至るまでの考察ステップについて記します。

1. まずは「全部イコール」の場合を考えよう

競技プログラミングでは、一見取り掛かるのが難しくても、限定的な場合の問題や、簡単にした問題の解法を手掛かりにできることがあります。

この問題では、いきなり \(d(p_{A_1}, p_{B_1}) < \dots < d(p_{A_{N(N-1)/2}}, p_{B_{N(N-1)/2}})\) を満たす点の配置を考えるのは難しいので、まずは「\(<\)」ではなく「\(=\)」の場合について考えてみましょう。つまり、どの 2 点間の距離も等しいような \(N\) 個の点の配置を求める、ということです。

\(N = 3\) の場合は、正三角形状に点を配置すればよいので、\(p_1 = (1, 0, 0), p_2 = (0, 1, 0), p_3 = (0, 0, 1)\) が条件を満たします。一般の \(N\) でも、同じように配置できます。

\[ \begin{aligned} p_1 & = (1, 0, \dots, 0) \\ p_2 & = (0, 1, \dots, 0) \\ & \vdots \\ p_N & = (0, 0, \dots, 1) \end{aligned} \]

このとき、どの 2 点間の距離も \(\sqrt{2}\) となります。

2. 微調整で距離を正しい順序にしよう

先ほどの「どの 2 点間の距離も同じ」解を微調整することで、距離を正しい順序にする戦略で行きましょう。ただし、一旦ここでは座標が整数という制約を忘れることにします。以下の図は、\(N = 3\) で正三角形状の点を微調整して \(d(p_2, p_3) < d(p_1, p_3) < d(p_1, p_2)\) の解を作るイメージです。

微調整の方法を数式で考えてみましょう。ずらす量を \(\epsilon_{i, j}\)（非常に小さい値）とすると、各点の座標は以下のようになります。

\[ \begin{aligned} p_1 & = (1+\epsilon_{1,1}, \epsilon_{1,2}, \dots, \epsilon_{1,N}) \\ p_2 & = (\epsilon_{2,1}, 1+\epsilon_{2,2}, \dots, \epsilon_{2,N}) \\ & \vdots \\ p_N & = (\epsilon_{N,1}, \epsilon_{N,2}, \dots, 1+\epsilon_{N,N}) \end{aligned} \]

このとき、点 \(p_i\) と \(p_j\) の距離は以下のようになります。

\[ d(p_i, p_j) = \sqrt{2 - (\epsilon_{i, j} + \epsilon_{j, i}) + (\epsilon_{i, 1} \epsilon_{j, 1} + \epsilon_{i, 2} \epsilon_{j, 2} + \dots + \epsilon_{i, N} \epsilon_{j, N})} \]

ここで、\(\epsilon_{i, j}\) が十分小さい場合、2 次の項 \((\epsilon_{i, 1} \epsilon_{j, 1}, \epsilon_{i, 2} \epsilon_{j, 2}, \dots, \epsilon_{i, N} \epsilon_{j, N})\) はそれよりはるかに小さくなり、距離の順序を考える上では無視できます。つまり条件は

\[\sqrt{2 - (\epsilon_{A_1, B_1} + \epsilon_{B_1, A_1})} < \sqrt{2 - (\epsilon_{A_2, B_2} + \epsilon_{B_2, A_2})} < \dots < \sqrt{2 - (\epsilon_{A_{N(N-1)/2}, B_{N(N-1)/2}} + \epsilon_{B_{N(N-1)/2}, A_{N(N-1)/2}})}\]

とみなせます。これを満たすように、例えば \((\epsilon_{A_1, B_1}, \epsilon_{B_1, A_1}) = (-0.000001, 0), (\epsilon_{A_2, B_2}, \epsilon_{B_2, A_2}) = (-0.000002, 0), \dots\) と設定すれば良いです。

3. 最後の仕上げ

前のステップで求めた答えには「座標が整数ではない」「座標が \(0\) 以上でない」という問題が残っています。

これは、拡大や平行移動によって解決できます。例えば、全体を \(10^6\) 倍した後、座標を一律に \(\frac{N(N-1)}{2}\) 足す、とする方法があります。このような対処を行うと、解説冒頭で述べたような形の答えが導かれます。

---

解答例

C++ での実装例は https://atcoder.jp/contests/arc172/submissions/50322419 です。

また、Python では以下のように実装できます。

# 入力を受け取る
n = int(input())
m = n * (n-1) // 2
a, b = [-1] * m, [-1] * m
for i in range(m):
	a[i], b[i] = map(lambda x: int(x)-1, input().split()) # 0-indexed に直して受け取る

# 各点対が何番目に遠いかを求める
r = [[-1] * n for _ in range(n)]
for i in range(m):
	r[a[i]][b[i]] = m - i

# 点の座標を求める
L = 10 ** 8
p = [
	[0 if i > j else L if i == j else r[i][j] for j in range(n)]
for i in range(n)]

# 答えの出力
for i in range(n):
	print(*p[i])