🔗 CF2179F Blackslex and Another RGB Walking

rating: 1982

Problem Statement

本題為一道 Run-Twice 類型的通信題 (Communication Problem)。

關於通信題 (Communication Problems)

這是一類新的題目類型，程式會被執行兩次，且遵循以下規則：

獨立執行：兩次執行之間的記憶體與變數狀態不會保留。
溝通機制：第一次執行的輸出內容，某種程度上會影響或成為第二次執行的輸入資訊（視題目而定），這是兩階段間唯一的溝通橋樑。
輸入輸出：兩次執行的輸入與輸出格式通常不同。
資源限制：兩次執行的時間與空間限制是分開計算的。例如時限 2 秒，只有當單次執行超過 2 秒才會被判 TLE（如果兩次各用 1.5 秒則是合法的）。
互動性：此類題目也可能同時是互動題 (Interactive)，需注意 IO 格式與 Flush 操作。

參考來源

https://codeforces.com/blog/entry/147996

題目簡述

給定一個二分連通圖，節點數 $n$ ，邊數 $m$ 。
第一階段 (Player A)：得知完整圖結構，需將每個頂點染成 R, G, B 三色之一。
第二階段 (Player B)：被隨機放置在 $v$ ( $v \neq 1$ )，無法得知自身編號與顏色，僅能看見所有鄰居的顏色。需根據鄰居顏色選擇移動到一個更靠近節點 $1$ 的鄰居。

Constraints

約束條件

$2 \le n \le 10^5, n-1 \le m \le 10^5$
$1 \le q \le 10^5$
$\sum d(v) \le 2 \cdot 10^5$
圖保證為二分圖且連通。
第二階段的輸入是 非適應性 (Non-adaptive) 的。

非適應性 (Non-adaptive)

這意味著 Player B 面對的詢問（起始位置）是固定的，不會因為 Player A 的染色方式不同而改變。換句話說，Judge 不會刻意針對你的染色結果去構造「最難」的詢問。

思路：BFS 分層染色

策略分析

由於我們需要引導 Player B 往節點 $1$ 移動，最直觀的想法是利用節點 $1$ 為其建立導航資訊。
我們可以使用 BFS 計算每個節點 $u$ 到節點 $1$ 的最短距離 $dist(u)$ 。
由於無法直接傳遞距離數值，我們利用 模運算 將距離映射到三種顏色：

Color(u) = \begin{cases} \text{Red} & \text{if } dist(u) \equiv 0 \pmod 3 \\ \text{Green} & \text{if } dist(u) \equiv 1 \pmod 3 \\ \text{Blue} & \text{if } dist(u) \equiv 2 \pmod 3 \end{cases}

為什麼這樣可行？

題目保證圖是 二分圖 (Bipartite Graph)。
在二分圖中，從一點出發的 BFS 分層結構非常嚴謹：任意邊 $(u, v)$ 連接的兩點，其距離起點 $1$ 的距離差恰為 $1$ 。即 $|dist(u) - dist(v)| = 1$ 。
這意味著，對於位於距離 $d$ 的節點 $v$ (目前所在位置)，其鄰居的距離只能是 $d-1$ (父節點方向) 或 $d+1$ (子節點方向)。

根據 $d \pmod 3$ 的染色規則，相鄰節點的顏色必然不同，且循環順序固定：
$\dots \to R \to G \to B \to R \to \dots$

若 $Color(v) = R$ ( $0$ )，鄰居可能是 $B$ ( $2$ , 父) 或 $G$ ( $1$ , 子)。
若 $Color(v) = G$ ( $1$ )，鄰居可能是 $R$ ( $0$ , 父) 或 $B$ ( $2$ , 子)。
若 $Color(v) = B$ ( $2$ )，鄰居可能是 $G$ ( $1$ , 父) 或 $R$ ( $0$ , 子)。

Player B 的決策

在第二階段，Player B 看到鄰居顏色集合 $S$ 。由於 $v \ne 1$ ，必然存在至少一個父節點 ( $dist = d-1$ )，即 $S$ 中一定包含父節點的顏色。

若 $|S| = 1$ ：
- 由於父節點 ( $d-1$ ) 與子節點 ( $d+1$ ) 的顏色差為 $2 \pmod 3$ ，它們的顏色 絕對不同。
- 因此，若只看到一種顏色，說明所有鄰居都是父節點（或者剛好沒有子節點）。
- 決策：直接移動到該顏色對應的任意鄰居。
若 $|S| = 2$ ：
- 看到 $\{G, B\}$ ：自己必為 $R$ ( $0$ )。父節點為 $B$ ( $2$ )。 $\to$ 往 Blue 走。
- 看到 $\{R, B\}$ ：自己必為 $G$ ( $1$ )。父節點為 $R$ ( $0$ )。 $\to$ 往 Red 走。
- 看到 $\{R, G\}$ ：自己必為 $B$ ( $2$ )。父節點為 $G$ ( $1$ )。 $\to$ 往 Green 走。

複雜度分析

時間複雜度： $\mathcal{O}(N+M)$ 用於第一階段 BFS；第二階段每個 Query 為 $\mathcal{O}(d(v))$ 。
空間複雜度： $\mathcal{O}(N+M)$ 儲存圖與顏色。

Code

from collections import deque

COLORS = "rgb"

def solve(player):
    if player == "first":
        n, m = map(int, input().split())

        g = [[] for _ in range(n)]
        for _ in range(m):
            u, v = map(lambda x: int(x) - 1, input().split())
            g[u].append(v)
            g[v].append(u)
        
        color = [''] * n
        vis = [False] * n
        vis[0] = True
        q = deque([(0, 0)])  # (u, d)
        while q:
            u, d = q.popleft()
            color[u] = COLORS[d % 3]
            for v in g[u]:
                if not vis[v]:
                    vis[v] = True
                    q.append((v, d + 1))
        print("".join(color))
    else:
        q = int(input())
        for _ in range(q):
            d = int(input())
            s = input()
            assert len(s) == d

            colors = sorted(set(s))
            if len(colors) == 1:
                c = colors[0]
            elif len(colors) == 2:
                if 'g' in colors and 'b' in colors:
                    c = 'b'
                elif 'r' in colors and 'b' in colors:
                    c = 'r'
                elif 'r' in colors and 'g' in colors:
                    c = 'g'
            print(s.find(c) + 1)

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

寫在最後

PROMPT

這裡什麼都沒有。