2020 全國賽驗題心得
筆者參與了本屆全國賽的驗題。驗題工作包含修正題目敘述與訂定時間限制，並 總是要 於必要時重出測試資料，前後花了一個多月才完成。讀者可以把這篇文章當作上篇 題解 的幕後花絮，簡單了解比賽題目是怎麼產生的，以及有哪些有趣的事情發生。由於筆者花最多時間在驗 pG 上，pG 會佔大部分的篇幅，還請見諒。 A. 礦砂採集 由於排序的 $O(n\log n)$ 和 quickselect 的 $O(n)$ 以比賽來說難以區分，一開始就只預期參賽者用排序 AC。一度想過是否把 $n$ 的上限拉到 $10^5$ 卡 $O(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$，給的 speci