🔗 CF2179G Blackslex and Penguin Migration

rating: 2342

Problem Statement

這是一道互動 (Interactive) 題。

題目簡述

有一個 n×nn \times n 的網格，每個格子裡住著一隻編號 11 到 n2n^2 的企鵝（每格恰好一隻）。
存在一個隱藏的初始網格 aa。你需要找出一個網格 bb，使得 bb 中任意兩隻企鵝的 Manhattan Distance 等於 aa 中對應兩隻企鵝的距離。
你可以進行最多 3n2+1503n^2 + 150 次詢問。每次詢問給定兩隻企鵝的編號 i,ji, j，系統會回傳它們在 aa 中的 Manhattan Distance。

Constraints

約束條件

  • 2≤n≤1002 \leq n \leq 100
  • ∑n≤500\sum n \leq 500

思路：尋找角點做為參考點，解聯立方程式

這題的核心在於利用 Manhattan Distance 的特性來定位。由於查詢次數限制約為 3n2+150>n3+n3n^2 + 150 > n^3 + n，這暗示我們可以進行三次「全體查詢」（即某個參考點到其他所有點的距離）和一次對某行、某列、或某對角線的查詢。

選擇相鄰角點做為參考點

設目標點座標為 (r,c)(r, c)，參考點座標為 (r0,c0)(r_0, c_0)，則曼哈頓距離為：

d=∣r−r0∣+∣c−c0∣d = |r - r_0| + |c - c_0|

由於絕對值的存在，直接解方程較為困難。但如果我們選擇網格的角點作為參考點，就能去掉絕對值符號：

  1. 若選取左上角 (1,1)(1, 1) 作為參考點，對任意點 (r,c)(r, c) 恆有 r≥1,c≥1r \ge 1, c \ge 1：

    d(1,1)=(r−1)+(c−1)=r+c−2d_{(1,1)} = (r - 1) + (c - 1) = r + c - 2

      ⟹  r+c=d(1,1)+2\implies r + c = d_{(1,1)} + 2 （我們得到了 r,cr, c 的和）

  2. 若選取右上角 (1,n)(1, n) 作為參考點，對任意點 (r,c)(r, c) 恆有 r≥1,c≤nr \ge 1, c \le n：

    d(1,n)=(r−1)+(n−c)=r−c+n−1d_{(1,n)} = (r - 1) + (n - c) = r - c + n - 1

      ⟹  r−c=d(1,n)−n+1\implies r - c = d_{(1,n)} - n + 1 （我們得到了 r,cr, c 的差）

結合兩式，即可唯一解出 rr 與 cc。這就是為什麼我們需要找到兩個相鄰角點的原因。

1. 尋找第一個角點 (xx)

我們需要找到網格的一個角點作為第一個參考點。這可以類比於求樹的直徑 (Tree Diameter) 的策略：

關鍵性質

在網格圖中，距離任意點最遠的點，必定是網格的四個角點之一。

  1. 任選一個點（例如編號 1），詢問它到其他所有點的距離。
  2. 找出距離最遠的點，記為 xx。
  3. 不妨假設 xx 的座標為 (1,1)(1, 1)。

此步驟約消耗 n2n^2 次查詢。

2. 尋找相鄰角點 (yy)

接著，我們需要第二個參考點來輔助定位。為了方便解方程式，最佳選擇是與 xx 相鄰的角點（即 (1,n)(1, n) 或 (n,1)(n, 1)）。

  1. 詢問 xx 到所有點的距離，記為 distxdist_x。
  2. 找出所有滿足 distx(v)=n−1dist_x(v) = n - 1 的點，構成候選集合 cands。
幾何直觀

在以 (1,1)(1, 1) 為原點的曼哈頓幾何中，距離為 n−1n-1 的點形成了一條對角線。這條對角線的兩個端點恰好是 (1,n)(1, n) 與 (n,1)(n, 1)。

  1. 在 cands 中，利用類似步驟 1 的方法（查詢其中一點到其他候選點的距離），找出距離最遠的一個端點，記為 yy。
  2. 不妨假設 yy 的座標為 (1,n)(1, n)。

此步驟包含一次全圖查詢 (distxdist_x) 與對角線上的點的查詢，總計約 n2+nn^2 + n 次。

3. 座標還原 (解聯立方程式)

最後，我們詢問 yy 到所有點的距離，記為 distydist_y，需要 n2n^2 次查詢。
現在對於任意企鵝，我們已知其到 (1,1)(1, 1) 的距離 dxd_x 與到 (1,n)(1, n) 的距離 dyd_y：

  • 由 x(1,1)x(1,1)：dx=(r−1)+(c−1)d_x = (r-1) + (c-1)
  • 由 y(1,n)y(1,n)：dy=(r−1)+(n−c)d_y = (r-1) + (n-c)

建立聯立方程式：

{dx=r+c−2dy=r−c+n−1\begin{cases} d_x = r + c - 2 \\ d_y = r - c + n - 1 \end{cases}

解此方程組可得座標公式：

座標公式

r=dx+dy−n+32r = \frac{d_x + d_y - n + 3}{2}

c=dx−dy+n+12c = \frac{d_x - d_y + n + 1}{2}

依此公式即可算出所有企鵝的座標 (r,c)(r, c)。

關於座標變換

題目要求輸出任意一組符合距離關係的 grid。雖然真實的網格可能經過旋轉或鏡像，但在 Manhattan Distance 幾何下，固定兩個角點 (1,1)(1, 1) 和 (1,n)(1, n) 所解出的座標系與原座標系是等距同構的（Isometry）。

複雜度分析

  • 時間複雜度：O(n2)\mathcal{O}(n^2)。
  • 空間複雜度：O(n2)\mathcal{O}(n^2)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def query(i, j):
    print(f"? {i} {j}", flush=True)
    return int(input())

def answer(ans: list[list[int]]):
    print("!", flush=True)
    for row in ans:
        print(*row, flush=True)

def solve():
    n = int(input())
    m = n * n

    # 隨便指定一點，網格中與其最遠的點必為角落的點 (類似兩次 DFS/BFS 求樹上直徑)
    u = 1
    dist1 = [0] * (m + 1)
    for v in range(1, m + 1):
        d = query(u, v) if v != u else 0
        dist1[v] = d

    # x 為角落上的一點，求其到所有點的距離
    x = max(range(1, m + 1), key=lambda v: dist1[v])
    distx = [0] * (m + 1)
    for v in range(1, m + 1):
        distx[v] = query(x, v) if v != x else 0

    # 與 x 距離為 n - 1 的點可以構成一條對角線，用類似前述的方式找出對角線上兩端的點 y
    cands = [v for v in range(1, m + 1) if distx[v] == n - 1]
    y = max(cands, key=lambda v: query(cands[0], v) if v != cands[0] else 0)

    disty = [0] * (m + 1)
    for v in range(1, m + 1):
        disty[v] = query(y, v) if v != y else 0

    # 此時找到了相鄰的兩個角落點 x 和 y
    # 不妨設 x = (1, 1), y = (1, n)，其他點的座標可以透過距離計算得出。
    grid = [[-1] * n for _ in range(n)]
    for v in range(1, m + 1):
        dx, dy = distx[v], disty[v]
        r = (dx + dy - n + 3) // 2
        c = (dx - dy + n + 1) // 2
        grid[r - 1][c - 1] = v
    answer(grid)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

這裡什麼都沒有。