2020 全國賽驗題心得
筆者參與了本屆全國賽的驗題。驗題工作包含修正題目敘述與訂定時間限制,並 總是要 於必要時重出測試資料,前後花了一個多月才完成。讀者可以把這篇文章當作上篇 題解 的幕後花絮,簡單了解比賽題目是怎麼產生的,以及有哪些有趣的事情發生。由於筆者花最多時間在驗 pG 上,pG 會佔大部分的篇幅,還請見諒。 A. 礦砂採集 由於排序的 Θ(nlogn) 和 quickselect 的 O(n) 以比賽來說難以區分,一開始就只預期參賽者用排序 AC。一度想過是否把 n 的上限拉到 105 卡 Θ(n2) 排序,想說這題就是個簽到題就算了,可惜仍有參賽者未能拿到滿分。 B. 村莊與小徑 看到 scoreborad 有人卡在最後一個 subtask,有點好奇究竟是單純的 bug 還是堅信 SPFA 的時間複雜度是 O(kE) 而狂傳。大概在 10 年前,筆者還在打 TOI 的時候,簡體中文網路上就流傳著 SPFA 時間複雜度只有 O(2E),快到可以作為 general 最短路徑演算法的都市傳說。筆者並不清楚為什麼許多中國人認為 Dijkstra 比 SPFA 難寫(筆者覺得正好相反)導致即使可能 TLE 也要寫 SPFA,不過總之請記得,如果一個題目能用 DAG 上 DP 或 Dijkstra 過,請不要用 SPFA。 C. 樣本解析 這題的交集關係部分寫得很繁瑣,但我們沒有辦法。本來打算用 ⊂ 表示 proper subset,實際上也有 ⊆ 這個符號,筆者認為就像 < 和 ≤ 一樣,不應有混淆的空間;然而偏偏有些作者在用「A⊂B」時,允許 A=B,可能導致參賽者混淆而放棄。也考慮過改用 ⊊ 符號,但這跟 \lneq 一樣相對罕見,考慮參賽者都是高中生很可能看不懂,只好全部改用中文敘述。 D. 水果包裝 筆者第一次看到題目後,在紙上推敲了許久(30 分鐘有)才得出 greedy 結論,很意外這題的答題狀況這麼好 ,好奇到底有多少人是用猜的 。不過有一等獎參賽者沒能拿到滿分,用心出 n 的數量級 10^5 的測資也有了價值 (? 原先這題 n 的上限只到 $100...