題目
pA
機器鴨
有兩個長度為 $n$ 的序列 $a, b$，有隻機器鴨會從原點依照這個序列移動，第 $i$ 個時刻，機器鴨會直線移動向量 $(a_i, b_i)$。
請重新排列序列 $a, b$，使得機器鴨能夠走回原點，並且移動過程中不會走到已經走過的點。無解輸出 $-1$。
$3 \leq n \leq 100$
$1 \leq |a_i|, |b_i| \leq 300$
$a_i \neq a_j$
Subtask
pB
惡地之路
$n$ 點 $m$ 邊帶權無向圖，每條邊有權重 $p_i$，定義從某點 $s$ 走到 $t$ 的票價為「路徑的權重和 $\times$ 經過的邊數」。
輸出從節點 $1$ 走到節點 $1 \sim n$ 的最小票價。
$1 \leq n \leq 2000$
$1 \leq m \leq 30000$
$1 \leq p_i \leq 10^6$
Subtask
pC
調色盤
有一長度為 $n$ 的序列 $c$，並有一數字 $k$。
$q$ 筆詢問 $(l, r)$，求有多少數對 $(i, j)$，滿足 $l \leq c_i \leq c_j \leq r \land |c_i| - |c_j| \leq k$。
$1 \leq n, k, q, c_i \leq 10^6$
Subtask
pD
告示牌
$n$ 個字串 $s_1,…,s_n$ 要寫到一個告示牌上，一個字串必定只能出現在一行，不可斷開。
在不超過 $k$ 行的情況下，告示牌最少需要有多寬？
$1 \leq k, \sum_{i=1}^{n} |s_i| \leq 2 \times 10^5$
Subtask
pE
變色蠑螈
一種魔法可用數對 $(a, b)$ 表示，代表可以將數字 $a$ 轉換成數字 $b$，或是反過來將 $b$ 轉換成 $a$。
現在有 $n$ 個要求，每個要求以 $(c, d)$ 表示，表示要將數字 $c$ 轉換成數字 $d$，請問最少需要學會幾種魔法才能達成上述要求。
$1 \leq n \leq 2 \times 10^5$
$1 \leq a, b, c, d \leq 10^9$
Subtask
比賽結果
Score：210／Rank：2nd
比賽過程
賽前 5 分鐘還跑去拉肚子，有點雷。
開場時網路爛掉，pE 點「下載題本」一直沒反應，於是重複點了 20 幾次，最後受不了去看其他題，正要看的時候剛剛的按鈕突然全部有了反應，於是我又連續 20 幾次點了「取消下載」，有夠靠北。
一樣先讀題，15 分鐘。比較慘的是我 pA 跟 pE 沒讀仔細，漏了關鍵限制，所以難度排序一整個大亂。
當時的難度排序：pA < pD < pB < pC < pE，幾乎把正確順序整個倒過來。
pA 以為鴨子移動過程可視為瞬間移動，想說只要 $\sum a_i$ 跟 $\sum b_i$ 都 $=0$ 那隨便排列 $a, b$ 都有高機率是正確答案。但我忘記是直線前進所以經過的路徑也不能有交點。
不只讀錯題想法還一點都不嚴謹，有夠笨。反正就以為是簽到題就開始寫下去了。
結果過程中碰到很弔詭的 bug，題本疑似有不乾淨的字元，我直接複製到 code 底下再貼到 console 竟然沒辦法輸入，於是又重新檢查模板、主程式，又換了好幾次寫法，最後改成手動輸入才終於安分地吃進數字。莫名其妙地又浪費二十分鐘在解決看不見的 bug。
上面那個是爛掉的輸入，下面是好的，有夠奇怪。
丟上去結果吃了 WA（賽後覺得吃 WA 不意外）。
00:40 pA 0分
賽中沒發現是題目讀錯，又耍智障了 15 分鐘結果一分都沒有
00:42 pA 0分
00:45 pA 0分
00:50 pA 0分
00:52 pA 0分
前面發生的一堆意外、pA 一直燒，加上過了一個小時卻一分都沒有。這時心態基本上已經崩了，完全不想繼續寫下去。觸犯比賽的大忌。
上廁所回來，心情恢復一些但沒完全回復，這時選擇繼續想其他題目。
pB 最短路徑，感覺可以直接砸 dijkstra，但沒有想清楚這其實是假解。
pC 完全不會，區間問題是我的痛點，只有 $O(nq)$ 雙指針的想法。
pD 裸二分搜，有信心直接 AC。
pE 讀題目的時候有讀到一個魔法可以從 a 變成 b 也可以反過來（無向邊），但放到腦中思考的時候自動變成了有向邊，於是就卡住，完全沒注意到這是並查集水題QQ。
這時我覺得 pD 雖然比較簡單，但我實作 dijkstra 比較穩定，於是就先從 pB 開始寫。10 分鐘後寫完就丟上去了。
01:11 pB 39分
有點慶幸總算有分數了，但我預期的是滿分，百思不解又繼續盯著 code，然後開始很智障地改一些沒有用處的實作小細節。這樣一拖又浪費了 30 分鐘
01:19 pB 39分
01:22 pB 39分
01:25 pB 39分
01:42 pB 39分
心態又更糟了，甚至一度認為是測資的問題。上完廁所後才終於肯跳題。
pD 穩定地刻完二分搜就丟上去了，一發 AC。應該先寫這題來穩住心態的。
01:57 pD 100分
接下來開始撈分，首先是 pA，這時候我才注意到我看錯題目，被自己笨死。
讀了子題，前 25 分可以暴力 $O((n!)^2 \times n^2)$ 拿掉，28 分觀察到可以先對 $a$ 排序，前 $n-1$ 個向量所形成的軌跡會是一個下凸包，最後則回到原點。於是改了一下剛剛的 code，丟上去 28 分。
02:05 pA 28分
這時候想刻 25 暴力分，沒想到除了要重寫外還需要刻向量模板。但我完全沒注意到 pC 更好撈而且分數更多，眼裡就只有 pA。
悲慘的是，我寫爛了，連範測都沒過。
剩下半個小時才驚覺時間不夠，這時才跳去 pC。邊寫邊想實作細節，幸好沒有出問題。
02:49 pC 37分
3 分只要加個特判就行了，多加幾行 if 丟上去我就去撈 pE 了，沒有去注意有沒有拿到，結果竟然沒有。
02:52 pC 37分
pE 的 6 分只要把 pair 丟進 set 就行了。
02:55 pE 6分
再來有 4 分是只要分 case，但因為我沒注意到邊是雙向的所以就沒有拿到QQ。
02:59 pE 0分
賽後檢討
一樣先列出這場出狀況＆耍智障的地方。
- 賽前拉肚子／開場網路爛掉／pA 輸入吃到奇怪字元。
- pA 讀錯題目。
- pB 單層 dijkstra 大假解，分層 dijkstra 可以拿 82 分，完整做法是 DP。對分層 dijkstra 還不是很熟，這是我的盲點。
- pD 最簡單沒有先寫。
- pE 思考的時候忘記是無向邊，整場被自己雷死。
- 糟糕的難度排序。
- pC 的 3 分沒拿到，是因為我在拿 37 分的時候為了加快 judge 結果，特意加了這行： 結果忘記拔掉qwq。
1
if (n > 10000) return 0;
總檢討
賽前
- 不要熬夜，11 點前就要上床。
- 可以寫些水題維持手感也穩住心態。
- 賽前一小時就要睡午覺，睡半小時起來才有時間讓腦袋暖機。
- 深呼吸告訴自己「我超電」、「我可以的」，但不是「我一定可以拿300分」。
策略修正
-
開場讀題 15 分鐘，讀題時務必連子題配分都要讀過一遍。
-
打模板的時間 5 分鐘，打的時候不要一直思考有什麼忘記打，浪費腦力，反正之後要用再補就好。
-
按照難度排序題目的技能要再加強。
-
時間分配：
- 觀察性質 3 分鐘
- 思考解法 7 分鐘
- 總實作時間 20 分鐘
- debug 10 分鐘
拿分間隔控制在 20 分鐘，最多不超過 30 分鐘。
停損點：思考 10 分鐘連 subtask 都沒想法就跳，卡了 40 分鐘一定要跳，不要一直想「"應該"還差一點就 AC 了」。 -
觀察性質：
- 注意變數範圍，誰特別大／特別小，作法 80% 跟它有關。
- 題目「保證」某種性質 $\rightarrow$，作法 99% 跟它有關。
- 常見手法：
- 對 OOO 排序
- 數值丟到數線上
- 數對 (a, b) $\rightarrow$ 二維平面
- 區間問題：離線、雙指針、單調性
-
思考解法：
- 寫下範測，釐清題目。
- 可以構造複雜點的測資幫助思考。
停損點：10 分鐘。
-
實作：
- 想到什麼 subtask 就寫什麼。
- 評估實作細節 2~3 分鐘。
- 分段 check 程式。
停損點：20 分鐘。
-
debug 時，先用 1 分鐘檢查有沒有智障 bug。
- 沒開 long long
- 陣列戳出界
- 寫好的函式忘記呼叫
- 0-base／1-base
- 忘記初始化
- ==打成=
構造測資，可以試試邊界測資，不要一直盯著 code。
有可能假解只是自己沒發現。
停損點：10 分鐘。
賽中心態調整
- 把比賽想成是跟出題者決鬥，AC 了代表運氣好決鬥獲勝，WA 了也只代表沒有打贏出題者，滿正常的事，絕對不要認為是因為自己實作爛實力爛，換一題跟他打就好。
- 不要急著想拿滿分，大部分的 AC 都是一點一點分數累積上去的，就算想到滿分解也是一樣。
- 丟一筆 submission 就去廁所，過半場吃點心。
- 換題的時候，一切重新 reset，剛剛發生了什麼事都不重要，不要掛在心上。
- 你炸掉大家也都會炸掉。
實用文章
