【心得】2022 NCPC 校內賽心得
前言
比賽前又失眠了，三點才睡著，八點半就爬起來但是卻意外的有精神。
校內賽前我們只有線上 virtual 過一次 (而且還偷懶沒有打滿 $5$ 小時)，甚至到今天我才第一次見到隊友林立上本人。
有好多隊伍都有人確診或隔離沒辦法比賽，像李佳樺超可憐直接變成單刷，也讓我們晉級的機會變大？
因為沒有準備 Codebook，所以直接用 BBQube 的，但好多我們根本不會的模板 QQ。
比賽
開場我先打 default code，游承桓跟林立上先讀題目。
很快游承桓就把 pA 丟給我了，是一道簽到題。
$\text{[0:06] pA }\color{green}{\text{AC}}$
林立上從後面看，發現 pK 也是水題，要輸出謝爾賓斯基碎形。
這題是遞迴的經典題，但卡了一點時間，因為我耍笨只輸出 $N$ 行，應該要輸出 $3^N$ 行。
$\text{[0:22] pK }\color{green}{\text{AC}}$ (首殺)
還蠻意外在卡了那麼久之後還能拿到這題的首殺
游承桓發現 pD 是中國剩餘定理的裸題，所以我就很開心的從 Codebook 抄了 extgcd 跟 crt 的模板，然後 submit。
$\text{[0:35] pD }\color{red}{\text{WA}}$
我以為是 crt 小的要放前面的問題，所以修改了之後又上傳一次。
$\text{[0:40] pD }\color{red}{\text{WA}}$
我們把 code 列印下來檢查是不是模板抄錯，也寫了暴力對拍都是對的，沒有找到 bug，所以就先跑去開 pG。
pG 一開始寫了五層的迴圈，但沒有注意到抽 $5$ 張牌是同時，與順序無關，所以以為這個方法行不通，因此跑去寫了 DP 的解，然後丟上去。
$\text{[0:45] pG }\color{red}{\text{WA}}$
一開始以為這題是 Output only，因為題本上似乎沒給範例測資，但後來有發現 judge 上面有測資可以下載，所以就稍微修改了一下然後上傳。
$\text{[0:59] pG }\color{green}{\text{AC}}$
賽後助教說 pG 的首殺跟官解都是直接用五層迴圈，顯然我在吃毒。
之後我們又開了很多題，pF 看起來是 flow，但是沒有想到要怎麼建圖。pH 是噁心的模擬題，要處理的細節蠻多的。pB 以為是奇怪的斜率優化 DP。
又過了一個小時後，我們決定把 pD 改成 __int128 試試看，雖然題目保證答案不超過 $2^{31}$ (一開始想說 long long 應該就夠了)。
$\text{[1:57] pD }\color{green}{\text{AC}}$
AC 後反而一臉矇逼？！
pH 雖然噁心，但是看起來是目前比較有機會做出來的題目，因此為了判斷 pH 的線段相交，我們從 Codebook 抄了將近 $100$ 行的模板，但是寫一寫就半放棄了，實作好噁心。
pE 可以發現對於一個連通塊 (高度相同) 他們的 spawn 值必定相同，並且一個點如果可以是 spawn 點，那麼該連通塊上所有高度比他小的的鄰居必須全部都是 spawn 點。
因此我刻了 DSU 來維護連通塊，再對高度做排序，由低往高枚舉，實作起來其實蠻乾淨的。
$\text{[2:50] pE }\color{green}{\text{AC}}$
耶，一發 AC！我們的排名也回到第 $5$ 名，第 $6$ 名跟我們 penalty 差不到 $20$ 分鐘。
這時候差不多封板了，pB 跟 pH 蠻多隊寫出來。
pB 我寫了從後面回推的 greedy，但很快被隊友發現是假解。後來林立上提出另一個 greedy，從對答案的貢獻下手。我們用這個方法試了範例測資都是對的，所以就跑去寫寫看。
$\text{[4:22] pB }\color{green}{\text{AC}}$
林立上 orz，想不到這樣就過了，難怪那麼多組比我們早寫出來，賽後題解出來也被證實這是一道水題，完全是我們想得太複雜了 (其實是古老 ABC round 的題目直接搬過來的)
剩下的時間就都拿去寫 pH 了，雖然範測有過，但是送出去後吃 WA 也沒有頭緒。賽後推測可能是因為 $K \leq 10^{18}$ 然後內積和外積都有乘法所以有可能會 overflow。
結果
AC：$6/11$
penalty：$756$
Rank $5$
結果 pF 真的是 flow，但要用到我還不會的 Konig’s Theorem。
開板後維持在 Rank $5$，第 $6$ 名的 penalty 只多我們 $30$ 分鐘，不過在開板前大概就有猜到可以晉級，因為後面沒有 $6$ 題的。
接下來 10/15 就要打 NCPC 決賽了，希望中間這段時間可以多 virtual 個幾場 (如果 NCPC 決賽不幸燒雞還有 TOPC 可以打)。