2020 全國賽驗題心得

筆者參與了本屆全國賽的驗題。驗題工作包含修正題目敘述與訂定時間限制，並總是要於必要時重出測試資料，前後花了一個多月才完成。讀者可以把這篇文章當作上篇題解的幕後花絮，簡單了解比賽題目是怎麼產生的，以及有哪些有趣的事情發生。由於筆者花最多時間在驗 pG 上，pG 會佔大部分的篇幅，還請見諒。

A. 礦砂採集

由於排序的 $\Theta(n\log n)$ 和 quickselect 的 $O(n)$ 以比賽來說難以區分，一開始就只預期參賽者用排序 AC。一度想過是否把 $n$ 的上限拉到 $10^5$ 卡 $\Theta(n^2)$ 排序，想說這題就是個簽到題就算了，可惜仍有參賽者未能拿到滿分。

B. 村莊與小徑

看到 scoreborad 有人卡在最後一個 subtask，有點好奇究竟是單純的 bug 還是堅信 SPFA 的時間複雜度是 $O(kE)$ 而狂傳。大概在 $10$ 年前，筆者還在打 TOI 的時候，簡體中文網路上就流傳著 SPFA 時間複雜度只有 $O(2E)$，快到可以作為 general 最短路徑演算法的都市傳說。筆者並不清楚為什麼許多中國人認為 Dijkstra 比 SPFA 難寫（筆者覺得正好相反）導致即使可能 TLE 也要寫 SPFA，不過總之請記得，如果一個題目能用 DAG 上 DP 或 Dijkstra 過，請不要用 SPFA。

C. 樣本解析

這題的交集關係部分寫得很繁瑣，但我們沒有辦法。本來打算用 $\subset$ 表示 proper subset，實際上也有 $\subseteq$ 這個符號，筆者認為就像 $<$ 和 $\leq$ 一樣，不應有混淆的空間；然而偏偏有些作者在用「$A \subset B$」時，允許 $A = B$，可能導致參賽者混淆而放棄。也考慮過改用 $\subsetneq$ 符號，但這跟 $\lneq$ 一樣相對罕見，考慮參賽者都是高中生很可能看不懂，只好全部改用中文敘述。

D. 水果包裝

筆者第一次看到題目後，在紙上推敲了許久（$30$ 分鐘有）才得出 greedy 結論，很意外這題的答題狀況這麼好，好奇到底有多少人是用猜的。不過有一等獎參賽者沒能拿到滿分，用心出 $n$ 的數量級 $10^5$ 的測資也有了價值 (?

原先這題 $n$ 的上限只到 $100$，給的 special judge 程式不僅時間複雜度 $\Theta(n^2)$ 還有 bug（直接用 %d 讀整數之類），最後筆者全部重寫 orz。測資部分有簡單卡 random：考慮 $n/2$ 個袋子裝 $1, 2, 4, \ldots, 2^{27}$，另外 $n/2$ 個袋子裝 $2^{28}-1$，並在這 $n$ 個袋子中隨機選擇 $n/2$ 個袋子追加放入 $10^9$，這樣只要裝有 $1, 2, 4, \ldots, 2^{27}, 10^9$ 的袋子的 $10^9$ 不是最後放入就會失敗。

E. 共同朋友

原始題目是給定 $K$，問有幾對 $(i, j)$ 的共同朋友數至少有 $K$ 個。由於出題者後來不認為高中生應該知道 __builtin_popcount() 或 std::bitset<N>::count()，但直接用 for 迴圈計算一個 word 包含幾個 bit 會 TLE，只好在比賽前一星期臨時把 $K$ 改成 $1$。

筆者也不認為一個參賽者應該知道這兩個東西，尤其前者是 gcc extension，更不應該成為「演算法」競賽的考點。然而 popcount 可以透過建 0~65535 表格快速得到，這個表格甚至能在 compile time 就計算完成，故像筆者一樣不喜歡這兩個東西的參賽者在 $K > 1$ 時也應該能做，且不困難。（筆者寫 code 時會盡量按照語言標準，避免使用 compiler extension 以確保在多數平台上都能正常運作；另，std::bitset<N> 無法動態調整大小，和筆者用多少開多少的習慣不合。）

追伸：其實筆者以外的兩位驗題者一致認為一個參賽者應該要知道 __builtin_popcount() （或者 cl.exe 提供的 __popcnt()）或 std::bitset<N>::count()，因此如果讀者懶得自己動手寫 popcount，建議熟悉這兩個 API，或者等到 std::popcount 正式加入 C++20。

F. 歡樂外送點

這題在比賽前，從出題者到所有驗題者都忽略了只能統計滿足 $x'\equiv y'\ (\operatorname{mod}2)$ 的整數點這件事，導致當 $(x, y, r) = (0, 0, 1), (0, 1, 1), (1, 0, 1), (1, 1, 1)$ 時，正確答案是 $3$，但標程均會給出 $4$。由於統計所有的 $(x', y') \in \mathbb{Z}^2$ 只有在四個 $45^\circ$ 正方形邊界均交於同一非格子點時才會出事，在隨機情況下很難遇到，所以實際上測資還是正確的，只是少了這個 corner case QAQ。

G. 矩陣相乘

其實找隨機向量測試並不是什麼新奇的手法，例如尋找一個複矩陣的 eigenvalue 的 power method。利用 $\mathbf{Cv} = \mathbf{A}(\mathbf{Bv})$ 的計算只需要 $O(n^2)$ 時間以降低整體計算時間的手法，也能在解聯立方程式的 conjugate gradient method 中看到（解 $\mathbf{Ax} = \mathbf{b}$ 但 $\mathbf{A}$ 不是正定時，改解 $(\mathbf{A}^*\mathbf{A})\mathbf{x} = \mathbf{A}^*\mathbf{b}$，但不直接求出 $\mathbf{A}^*\mathbf{A}$ 而是在每次迭代計算形如 $\mathbf{A}^*\mathbf{Ax}$ 的東西）。但一般高中生其實連矩陣乘法都不熟悉了（畢竟數學要到高三才教），遑論要活用上述的手法，而本題確實也是唯一沒有參賽者滿分的題目。

筆者負責這題的測資。原先這題 $n \leq 800$，出題者只表示絕對不能讓 $\Theta(n^3)$ 過，然而筆者的 $\Theta(n^3)$ 乘法在加了各種優化（e.g. 用 gcc 提供的 128-bit integer 累加 $a_{ik}b_{kj}$ 後再取 mod 以得到 $c_{ij}$，以及將 $\mathbf{B}$ 轉置以獲得更好的 cache locality 等）後可以輕鬆地在 2 秒內跑完。最早兩份標程（出題者與筆者各一份）的 $O(n^2 \log n)$ 做法都用了 $\Theta(n^2 \log n)$ 次的 mod 運算，即使把 $n$ 拉高至 $4000$ 也未能顯著地拉開執行時間（筆者的程式 30 多秒，出題者 40 多秒，而 $\Theta(n^3)$ 雖然最長，也不到 50 秒），最後只好把 $p$ 的上限調低確保 $np^2$ 仍在 64-bit integer 裡面，修改標程使 mod 次數降為 $O(n\log n)$，並直接在題本說明「想過這題就不要做太多次 mod」。

在確定 $O(n^2 \log n)$ 和 $\Theta(n^3)$ 能拉開後，暫時將 $n$ 的上限降低至 $3000$，並重出了測資，時限設為 7.5 秒；另，由於 $p$ 不大時必須增加測試次數，為了減少標程時間，就把 $p$ 的下限提高至 $3001$。然而主辦方認為測資檔太大，希望能降低 $n$ 的上限與時限；另一方面，出題者表示 subtask 2 卡了只挑 1 個測試向量的演算法，希望 subtask 3 能卡只挑 2 個的（在後段有仔細說明）。和出題方和主辦方的交涉過程中，不斷地更新測資，最後總算定下 $n$ 的上限為 $2800$，並確認時限為 6.5 秒；此時加入只能用於 subtask 1 的剪枝的 $\Theta(n^3)$ 程式的執行時間在 7.5 秒上下（儘管 subtask 2/3 即使沒 TLE 也會 WA），可說是算得剛剛好。因為這題的測資檔很肥，光是最後版本就超過 900 MB，幾度弄壞了 gitlab，最後 merge 了好幾次才成功進入 master。

以下簡單介紹測資怎麼出的。一個簡單的方法是生出 $\mathbf{A}$ 和 $\mathbf{C}$，其中 $\mathbf{A} \in GL(n, \mathbb{Z}_p)$，這樣一來只要取 $\mathbf{B} = \mathbf{A}^{-1}\mathbf{C}$，就有 $\mathbf{AB} = \mathbf{C}$。但注意這種生成方式只要 $\mathbf{C}$ 有某個 column 全為 $0$，$\mathbf{B}$ 在對應的 column 就是 $0$，而這會讓剪枝仔有機可乘，not cool。由於 $(\mathbf{AB})^T = \mathbf{B}^T\mathbf{A}^T$，我們挑的 $\mathbf{C}$ 要嘛得滿足每個 row 皆不為 $0$（此時生 $\mathbf{B} \in GL(n, \mathbb{Z}_p)$ 取 $\mathbf{A} = \mathbf{CB}^{-1}$），要嘛得滿足每個 column 皆不為 $0$（此時生 $\mathbf{A} \in GL(n, \mathbb{Z}_p)$ 取 $\mathbf{B} = \mathbf{A}^{-1}\mathbf{C}$）。這個生成方式相對簡單，唯一的缺點是 $\mathbf{A}$ 和 $\mathbf{B}$ 至少有一個是 invertible；為了防止有數值線代專家利用這點來 hack（雖然不太可能），還是生了一筆 $\operatorname{rank}\mathbf{A} = \operatorname{rank}\mathbf{B} = \operatorname{rank}\mathbf{AB} = n-1$ 的測資在 subtask 2 中。

Subtask 1 除了詳解中介紹的 $O(n^2)$ 方法外，也能令 $t = 1$ 取 $\mathbf{v_1} = (1, 1, \ldots, 1)^T$，再套用原隨機演算法，可以 $100\%$ 得到正確的答案。實際上不只是 $(1, 1, \ldots, 1)^T$，任意 $\mathbf{v_1} \in \mathbb{Z}_p^n$ 只要每個分量都不是 $0$，就能做到這件事。筆者在 subtask 2 放了一個 $\mathbf{C}$，其中 $n = 2800, p = 2801$， $$\mathbf{C}_{1:n; 1:2} = \begin{pmatrix}1&1\\1&2\\\vdots&\vdots\\1&2800\end{pmatrix},$$ 且其他 entry 都是 $0$。這樣只要 $(\mathbf{v_1})_1$ 和 $(\mathbf{v_1})_2$ 都不是 $0$，執行演算法時就會有某個 row 被判定為 $0$，因為 $\mathbf{C}$ 有一列叫作 $(1, -(\mathbf{v_1})_1(\mathbf{v_1})_2^{-1}, 0, 0, \ldots)$，讀者可自行驗證這個 row vector 和 $\mathbf{v_1}$ 乘起來恰為 $0$。注意題目定 $n$ 的上限為 $2800$ 而 $2801$ 剛好是質數，恰好可以拿來生成這個 case（其實這就是 $2800$ 的由來：選一個看起來比較不可疑的數 $N$，滿足 $N<3000$ 且 $N+1$ 為質數）。

回想一下，在 subtask 2 中，只要挑對兩條向量，就能 $100\%$ 得到正確的答案。由於被出題者發現 subtask 2 可以卡 $t = 1$，便希望能放卡 $t = 2$ 的測資在 subtask 3 中，而這 exactly 就是為什麼 $p$ 的下限被設為 $37$ 這個可疑數字了。設測試向量 $(\mathbf{v_1})_{1:3} = (a_1, b_1, c_1), (\mathbf{v_2})_{1:3} = (a_2, b_2, c_2)$。簡單算一下可以發現，只要 $$x: y: z = \begin{vmatrix}b_1&c_1\\b_2&c_2\end{vmatrix}: \begin{vmatrix}c_1&a_1\\c_2&a_2\end{vmatrix}: \begin{vmatrix}a_1&b_1\\a_2&b_2\end{vmatrix}$$ 便有 $a_1x+b_1y+c_1z = a_2x+b_2y+c_2z = 0$。因此需要放置以下這些 row：

• $(1, x, y, 0, \ldots)$，其中 $x, y \in \mathbb{Z}_p$。
• $(0, 1, x, 0, \ldots)$，其中 $x \in \mathbb{Z}_p$。
• $(0, 0, 1, 0, \ldots)$。

所以 $n$ 必須大到足以放入這些 row，也就是 $$p^2 + p + 1 \leq n.$$ 另一方面，nontrivial entry 不能超過 $2n$ 個，而統計一下可以發現上面這些 row 共有 $3p^2$ 個 nontrivial entry，故也必須滿足 $$3p^2 \leq 2n.$$ 最後，每條 row 至少要有一個非 $0$（其實改成每條 column 也行，只是不會比較好），所以必須有 $$2n-3p^2 \geq n-(p^2+p+1).$$ 代入 $n = 2800$ 解上面三式，推出最大的 $p$ 為 $37$，不能再大了。

追伸一：為了方便說明，上述的 $\mathbf{C}$ 其實是簡化過的，比賽時的 $\mathbf{C}$ 有做進一步的加工。例如實際上卡 $t = 1$ 的 $\mathbf{C}$ 唯二的 nontrivial column 並不是在 $1$ 和 $2$，而是在 $3$ 和 $4$，且每個 row 都被隨機乘上了某個非 $0$ 數。

追伸二：在推出 $p$ 的下限必須為 $37$ 或更低後，也生了 $p=37$ 的其他測資，這時出題者的標程居然 WA 了。加上 srand(time(nullptr)) 後，測 $10$ 次 WA $10$ 次，慘不忍睹。仔細看了 code 才發現原來出題者的程式並不是設定 $t = 5$，而是跑 $5$ 次 $t = 1$ 後取聯集；這就是為什麼詳解中特別對這種情況做估計。

追伸三：設 $\mathbf{u}, \mathbf{v}$ 為兩向量，有人會把 $\mathbf{v}^T\mathbf{u}$ 稱作 $\mathbf{u}$ 和 $\mathbf{v}$ 的內積，但這是錯的。同樣地，兩矩陣乘積 $\mathbf{AB}$ 在 $(i, j)$ 元素的值也不該被稱為 $\mathbf{A}$ 的第 $i$ 列與 $\mathbf{B}$ 的第 $j$ 行的內積。故事是這樣的：當 $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ 時，兩者的 canonical inner product $\langle \mathbf{u}, \mathbf{v} \rangle$ 確實是 $\mathbf{v}^T\mathbf{u}$，也就是 $u_1 v_1 + u_2 v_2 +\ldots + u_n v_n$；然而若 $\mathbf{u}, \mathbf{v} \in \mathbb{C}^n$（複向量），$\langle \mathbf{u}, \mathbf{v} \rangle$ 的定義其實是 $\mathbf{v}^*\mathbf{u} = u_1 \overline{v_1} + u_2 \overline{v_2} + \ldots + u_n\overline{v_n}$，其中 $^*$ 代表 conjugate transpose（將每個元素取共軛後轉置）。至於為什麼複向量的內積不被定義成逐項相乘後相加，簡單來說就是性質太差，能做的事情不多（想想為什麼不能比較兩複數的大小關係）。舉例來說，我們希望一個向量 $\mathbf{u}$ 和自己內積後是一個 $\geq 0$ 的數，代表 $\mathbf{u}$ 的長度平方，且只在 $\mathbf{u} = \mathbf{0}$ 時才是 $0$。不難檢驗 $(z_1, z_2, \ldots, z_n)^T$ 和自己內積為 $|z_1|^2 + |z_2|^2 + \ldots + |z_n|^2$，與我們熟悉的長度平方一致；但如果把內積定義成單純的逐項相乘後相加，只會得到一個奇怪的複數。事實上，內積也只能在 real/complex vector space 上定義，而這道題目考慮的是 $\mathbb{Z}_p^n$，自然沒有內積的結構（或者說沒有合適的定義）。

H. 跑跑遊戲場

筆者在試做題目時，卡在這題的時間最久，浪費了不少時間尋找合適的 divide-and-conquer 演算法，很驚訝現場有人能拿到滿分。由於這題的各種小細節非常多，最後生了 $200$ 多筆測試資料，希望有卡掉所有不小心寫出的小 bug。

I. 黑白機

這題答題狀況比預期的差，推測是被放在最後一題的關係。由於筆者除了寫標程，沒有參與這題的題敘修訂與測資生成，就讓本文在此結束吧。