2021台灣國際資訊奧林匹亞初選 解說 (2021 TOI入營考 Editorial)

A: 原始人排序

可以用 STL 提供的 stable_sort 再加上自己手寫的 compare function:

stable_sort(ar, ar+n, [](int x,int y) {
  return __builtin_popcount(x) < __builtin_popcount(y);
});

其中:

B: 掃地機器人

預設解法：

觀察

  1. 機器人只往右走不會比較差 (來回走會造成時間浪費)
    • 如果機器策略是【掃1分鐘教室1】 ⇨ 【掃2分鐘教室2】 ⇨ 【掃1分鐘教室1】，那不如一開始就掃教室1掃2分鐘。
  2. 機器人最終停在哪個教室不一定
  3. 由以上兩點，可以得知機器人花在移動的總時間是由終點決定的
    • 如果最後停在教室 e，那麼可以花在掃除的時間為 m - t1 - t2 - … - te-1

做法1

「如果最後停在教室 e，那麼可以掃除的總時間為 k = m - t1 - t2 - … - te-1」

可以得到以下算法：

// 扣掉移動時間後，有 k 分鐘打掃前 e 個教室最大蒐集灰塵量
long long collect_dust(int e, int k) {
  priority_queue<pair<int,int>> pq; // 維護 (目前蒐集得到的灰塵量, 教室id)
  long long result = 0;

  for (int i=1; i<=e; i++) {
    pq.emplace(s[i], i);
  }
  for (int t=1; t<=k; t++) {
    if (pq.empty()) break; // 所有 >= 0 的灰塵都被掃完了

    int dust, classroom;
    tie(dust, classroom) = pq.top();
    pq.pop();

    result += dust;
    if (dust - d[classroom] > 0) { // 下一次掃除的灰塵量 > 0 的話
      pq.emplace(dust - d[classroom], classroom);
    }
  }
  return result;
}

做法2

跟做法 1 一樣考慮固定走到教室 e 的情況

對於一個灰塵量 x，可以統計教室裡可以掃到這個灰塵量的總分鐘數：

給一個終點 e，灰塵量 x，可以 O(n) 算出對應的 a 和 b

using PLL = pair<long long,long long>;

PLL dust_to_time(int e, int x) {
  long long a = 0, b = 0;

  for (int i=1; i<=e; i++) if (s[i] >= x) {
    if (d[i] == 0) {
      return PLL (LLONG_MAX, LLONG_MAX);
    }

    a += (s[i] - x) / d[i] + 1;
    if (s[i] % d[i] == x % d[i]) { // 最小的那分鐘剛好掃到的灰塵量是 x
      b++;
      a--;
    }
  }
  return PLL(a, b);
}

注意到 (a, a+b) 都會隨著搜索的 x 遞增而遞減。因此可以二分搜索 x

每次二分搜索的時間複雜度為 O(n log S)，乘以 n 個終點，為 O(n2 log S)。

C: 粉刷護欄

預設解法:

subtask1

枚舉所有選木板的 2n 種可能，每次花 O(n) 檢查選的木板集合是不是合法。

複雜度: O(2n × n)

subtask2

正式一點來定義這個問題：

如果只求 k 的值就是單純的求 LIS 長度，但因為這裡有字典序最大的條件會稍微複雜一點

DP

for (int i=n; i>=1; i--) {
  dp[i] = 1;
  nxt[i] = -1;
  for (int j=i+1; j<=n; j++) if (w[j] > w[i]) {
    if (dp[j] == dp[i]-1 && a[j] > a[nxt[i]]) { // 一樣長，比字典序
      nxt[i] = j;
    } else if (dp[j]+1 > dp[i]) { // 更長，直接更新最佳解
      dp[i] = dp[j] + 1;
      nxt[i] = j;
    }
  }
}
int k = *max_element(dp+1, dp+n+1);

還原解的時候起點是 dp 值 = k 且 a 值最大的那個。複雜度為 O(n2)

subtask3

nxt 有不少 ad-hoc 的求法，這裡介紹其中一種

D: 乘車時間

預設解法

這題的部分分不好拿，除了 subtask4 以外都互相不包含其它 subtask 的做法，得分開實作。

subtask1

對於每筆詢問，可以 BFS/DFS O(n) 處理。注意換車的時候小心處理下次能坐到車的時間即可。

複雜度 O(qn)

subtask2

「每個整數分鐘都會發車」，也就是說不需要考慮轉車完但車子還沒來的情況。 因此答案會等於「經過的邊權總和 + 經過點數 - 1」。 其中 (經過點數-1) 是所需的換車時間。

這個問題答案可以透過求樹上 LCA(最近共通祖先) 順便得出，有不少的作法這裡就省略解釋了。 推薦讀者至少要會基於倍增的作法 (參見 “Another easy solution in <O(N logN, O(logN)>” 一節)。

複雜度 O(n log n + q log n)

subtask3

給定的路線網為一條線。從這個 subtask 開始需要考慮出發時間的性質：

將所花的時間分成乘車、轉車、等車三個部份考慮。 考慮某個從 x 到 y 的路線，可以發現任意時間出發花在轉車以及乘車的時間是固定的，造成費時不同的主因是等車的班距。舉個例子:

觀察：如果所有車的班距都一樣(前後一班車都是 3 分鐘一班)，好像就只需要考慮一種可能了?

算法:

複雜度 O(n log n + q log n)

subtask4

首先任意找一個樹根，合併 subtask2 的倍增作法以及 subtask3 處理出發時間的方法，可以維護以下的 DP:

要特別小心處理的是 down 和 up 的 DP 方法並不太一樣。 維護表格的大小為 log n × n × 60，每次查詢可以在 O(log n) 得到解答。複雜度為 O(n log n + q log n)

E: 密室逃脫

建議看此題解法前的預備知識：

E - 解法一覽

E - subtask 配分

E - 一般二分圖匹配解法

建一張二分圖 G=(X,Y,E)，X, Y 各有 n 個點。其中

用二分圖最小覆蓋的概念來解題，把「選點」進最小覆蓋集合這個動作看成

可以看出 Ai,j ≤ 1 時這題跟二分圖最小覆蓋完全等價。USACO Asteroids 就是一個例子。

根據 Kőnig’s theorem，二分圖最小點覆蓋 = 二分圖最大匹配，兩者互為 Primal-Dual 問題。

因此這題最小點覆蓋可以用一般二分圖匹配或 flow 來計算，現在剩下的問題是如何輸出可行解方案。下面將用最小割的角度來解釋如何得出可行解

s-t Cut

[定義] 一張帶邊權的有向圖 G=(V,E)，我們可以把點集 V 分成兩個互斥的集合 S,T。定義 G 的 s-t 割 C=(S,T) 滿足：

另外我們可以定義割邊：

最小權重的 s-t 割被稱為「最小 s-t 割」。根據 max flow - min cut theorem，從 s 到 t 的最大流與它的最小 s-t 割答案是相等的。

紅色=S點集，藍色=T點集。上面割權重 = 9+12 = 21。

割權重 = 6+4+2 = 12。是最小的割。

最大二分匹配 → 最大流

由於這個模型很常見這裡就省略說明了。注意這裡用的模型中間流量是無限大不然會影響找解的正確性，理由在之後的頁面會說明

最小點覆蓋 → 最小割

注意: 雖然說中間邊權設 1 跑出來的最大匹配數量是對的，但從最小割的觀點來說這個模型是錯的，並且在找對應最小覆蓋解的時候也會出錯。

最大流 → 最小割

[定理]: 若 C(S, T) 是一個 s-t 割，則滿足

  1. 在殘流網路(residual network)裡，S 集合沒有連向 T 的出邊
  2. 在殘流網路裡，T 沒有 S 連過來的入邊

換句話說: S 到 T 的邊都應該是流滿的。根據上面的定理，我們可以從最大流的殘流網路裡找到對應的割

最大流 → 最小割

[性質]:

牛刀小試: 給一張二分圖以及他的最大匹配。找出一個字典序最小的最小點覆蓋(UTPC 2013, K)

由上面的定理及性質，我們可以在求出二分匹配之後推出原本最大流作法的殘流網路，並推算出最小割的集合以及每個點是否在最小覆蓋裡面。

另解: 2-SAT

由於每個匹配邊的兩端點只會恰好有一點在最小覆蓋的集合裡面，我們可以利用這個性質來建出 2-SAT 的模型。這個模型對應到的解也會是最小點覆蓋。簡單的建模：

2-SAT 要判斷有無解比較簡單，但要輸出可行解則會複雜很多。可以參考 POI 的 peaceful commission (PL)。

E - 費用流與匈牙利解法

Outline:

在邊沒有帶非負權的情況下，這題的所求和最大帶權的二分匹配相等。有兩種方法可以理解這個問題：

  1. Egerváry’s theorem：w-vertex cover 和 w-weight matching 恰為線性規劃的對偶問題
  2. 匈牙利算法的過程中，w-vertex cover 滿足的條件與算法中每個點的 label 條件相同

又因為這題是完全二分圖且有 $A_{i,j} \ge 0$ 的限制，因此最大權二分匹配 = 最大權完美二分匹配。

匈牙利解法

題目定義的行、列可行解剛好就是匈牙利算法中 feasible label 的定義，直接輸出 labeling 就是一組可行解了

要注意的是要解最後一個子題時間要求到 $O(n^3)$，網路上有不少模板都是 $O(n^4)$ 的作法。

費用流解法

套用之前二分匹配做法的最大流模型，並為中間的邊加上輸入矩陣的 cost。可以發現二分圖的帶權匹配與最大費用流等價，這個模型也很常見所以在這裡就不多做解釋了。 但目前還有兩個問題尚未解決：

  1. 一般的最小/最大費用流作法是 $O(n^4)$，這對最後一個 subtask 來說並不夠快
    • $O(n^4)$ 的細項: 需要做 $O(n)$ 次最短路增廣，每次增廣要花 $O(|V||E|) = O(n^3)$ 的時間。
  2. 輸出可行解的方案

為了解決上面兩個問題，下面會介紹一個稱為 potential 的概念。

Potential - 定義

給定一張無負環的邊帶權圖 $G = (V, E, w)$，我們說 $\pi$ 是 G 的一個合法的 potential function 代表它滿足以下條件：

[性質]：令 $\delta_s(x)$ 為某一頂點 s 為起點至 x 的最短距離，若 s 可以連通到所有點，則 $\delta_s$ 是一個合法的 potential function。

[說明]：由三角不等式可以得知，對任意邊 $(x, y) \in E$ 有 $\delta_s(x) + w_{x,y} \ge \delta_s(y)$，移向可以得到與定義相同的結論。

Potential - 應用

定義: $\pi(x) + w_{x,y} - \pi(y) \ge 0$

Potential - 應用2

一個很有名的應用是可以用來求所有點對最短路的 Johnson’s algorithm

概念上是因為做非負權最短路的 Dijkstra 比負權最短路算法的 Bellman-Ford/SPFA 還要快許多。 因此這裡選擇只做一次 Bellman-Ford 將所有邊權調整成非負，其它次的最短路用 Dijkstra 來加速。

類似地，也可以用相同的概念在稀疏圖上得到找最小環 $O(nm \log n)$ 的結果，並且在 2016 年這個算法被改進到 O(nm)。 (link1, link2)

Potential - 費用流應用

和全點對的最短路一樣，最小費用流也需要透過多次最短路來增廣流量。但有幾個問題存在：

[引理]: 對一網路 G=(V,E)，令 $G_f$ 為增廣數次後的最小費用流的殘流網路， 且殘流網路經過 potential function $\pi$ 調整後的邊權為 $a_{\pi}(e) \ge 0$ $(\forall e \in E_f)$。 對所有 $v \in V$ 令 $\delta_{\pi}(v)$ = 從 s 出發經調整後邊權 $a_{\pi}$ 走到 $v$ 的最短路。 若 $G_f$ 經由某條最短路增廣殘流網路變成 $G_{f^{\prime}}$，則 $\pi^{\prime} = \pi + \delta_{\pi}$ 是 $G_{f^{\prime}}$ 合法的 potential function。

[證明]: 對 $G_{f^{\prime}}$ 的所有邊 $e = (u, v)$ 及新調整的權重 $a_{\pi^{\prime}}(e) = a_{\pi}(e) + \delta_{\pi}(u) - \delta_{\pi}(v)$， 考慮以下兩種情況：

  1. 若 $e \in E_f$ (增廣前就有的邊)，那麼由原圖的三角不等式可得 $a_{\pi}(e) + \delta_{\pi}(u) - \delta_{\pi}(v) \ge 0$
  2. 若 $e \notin E_f$ (e是增廣後才多出來的反向邊)，那可以知道對應的反向邊 $\overleftarrow{e} = (v, u)$ 必定是增廣前最短路的一條邊
    • 由最短路定義，可得 $\delta_{\pi}(v) + a_{\pi}(\overleftarrow{e}) = \delta_{\pi}(u)$
    • $a_{\pi^{\prime}}(\overleftarrow{e}) = a_{\pi}(\overleftarrow{e}) + \delta_{\pi}(v) - \delta_{\pi}(u) = 0$
    • $a_{\pi^{\prime}}(e) = - a_{\pi^{\prime}}(\overleftarrow{e}) = 0$

最小費用流的算法:

上面算法需要執行 O(n) 次 Dijkstra 與一次 Bellman-Ford。其中 Dijkstra 用 priority_queue 實作的複雜度為 $O(n^2 \log n)$， 但考慮到給定的圖為稠密圖，可以省略 priority_queue 直接用迴圈枚舉距離最小的點，複雜度變為 $O(n^2)$。

因此這裡得到了一個 $O(n^3)$ 的算法。(註: $O(n^3 \log n)$ 是預設會超時的)

最小費用流 → 找解

考慮做完所有增廣路後的殘流網路 $G_f = (V_f, E_f)$，以及 $A_{i,j}$ 所對應的邊 $e = (u, v, -A_{i,j})$，最後的 potential $\pi$ 及調整後的權重 $a_{\pi}$。

因此找完解之後的 potential function，將二分圖中右邊點的 potential * -1 就是題目所求的 w-覆蓋方案了。

可行解的其它求法

假設找到一組可能是負數的可行解 $\{r_i\}$ 與 $\{c_i\}$ 那麼：

可行解的條件: $r_i + c_j \ge A_{i,j}$

可行解整理

上面三個算法其實殊途同歸，有興趣的讀者可以想想看這三種算法之間的關係

小故事: 測資

為了要讓優化過的 SPFA 和 $O(n^4)$ 匈牙利能順利超時，有幾筆測資是這樣生成的:

for (int i=1; i<=n; i++) {
  for (int j=1; j<=n; j++) {
    if (i<=j) {
      a[i][j] = 4*n*n + (j-i)*(j-i);
    } else {
      a[i][j] = random.randint(0, n*n);
    }
  }
}

通常 online judge 上二分圖帶權匹配的題目用 $O(n^4)$ 作法都可以過， 建議寫模板的時候可以多測這筆測資做參考

存邊

通常存稀疏圖邊有兩種知名的方法，第一個是用 vector:

vector<Edge> e[M];
void add_edge(int a, Edge x) {
  e[a].push_back(x);
}

另一個是俗稱前向星的鏈表儲存方式：

Edge e[M];
void add_edge(int a, Edge x) {
  e[eid] = x;
  e[eid].next = first[a]; first[a] = eid++;
}

這題有 tester 實作了一份非常慢的前向星 + potential 優化費用流解， 在實測時這份解跑的比 vector 存邊還要慢了至少 15 倍以上。 因為實在慢到快跟 $O(n^4)$ 的解一樣了就只好讓這份解 TLE 了。 這是少數理論複雜度正確但卻會超時的例子， 同時也是最後一個 subtask 配分很低的主要原因之一。

更詭異的一點是，當測試時把 judge worker 降到 1 以後 (取消平行 judging)， 其它解執行時間並沒有明顯的差異， 但這個原本慢 10 多倍的解突然變成只慢 2 倍左右了。 造成這樣現象的原因雖然沒有很確定，但推測應該是跟 CPU locality cache 以及平行 judge 造成 hit rate 太低有關係， 因為用鏈表存的時候記憶體並不連續。 類似地，這次的 D 其實也有一樣的問題：

int dp1[16][N][60];
int dp2[N][60][16];

經比較這兩種表格的開法第一種大概快約 2 倍左右， 原因是因為記憶體的配置和 DP 的順序一樣（註：兩種開法都可以拿滿分）。 如果有超時問題卻找不到原因的人可以注意一下是不是有類似的問題在。

tl;dr：寫 flow 模板的時候可以的話還是用 vector 吧。

This site is open source. Improve this page.