【心得】2022 NCPC 校內賽心得

前言

比賽前又失眠了，三點才睡著，八點半就爬起來但是卻意外的有精神。

校內賽前我們只有線上 virtual 過一次 (而且還偷懶沒有打滿 小時)，甚至到今天我才第一次見到隊友林立上本人。

有好多隊伍都有人確診或隔離沒辦法比賽，像李佳樺超可憐直接變成單刷，也讓我們晉級的機會變大？

因為沒有準備 Codebook，所以直接用 BBQube 的，但好多我們根本不會的模板 QQ。

比賽

題本連結
題解

開場我先打 default code，游承桓跟林立上先讀題目。

很快游承桓就把 pA 丟給我了，是一道簽到題。

林立上從後面看，發現 pK 也是水題，要輸出謝爾賓斯基碎形。

這題是遞迴的經典題，但卡了一點時間，因為我耍笨只輸出 $$ 行，應該要輸出 $$ 行。

$$ (首殺)

還蠻意外在卡了那麼久之後還能拿到這題的首殺

游承桓發現 pD 是中國剩餘定理的裸題，所以我就很開心的從 Codebook 抄了 extgcd 跟 crt 的模板，然後 submit。

$$

我以為是 crt 小的要放前面的問題，所以修改了之後又上傳一次。

$$

我們把 code 列印下來檢查是不是模板抄錯，也寫了暴力對拍都是對的，沒有找到 bug，所以就先跑去開 pG。

pG 一開始寫了五層的迴圈，但沒有注意到抽 $$ 張牌是同時，與順序無關，所以以為這個方法行不通，因此跑去寫了 DP 的解，然後丟上去。

$$

一開始以為這題是 Output only，因為題本上似乎沒給範例測資，但後來有發現 judge 上面有測資可以下載，所以就稍微修改了一下然後上傳。

$$

賽後助教說 pG 的首殺跟官解都是直接用五層迴圈，顯然我在吃毒。

之後我們又開了很多題，pF 看起來是 flow，但是沒有想到要怎麼建圖。pH 是噁心的模擬題，要處理的細節蠻多的。pB 以為是奇怪的斜率優化 DP。

又過了一個小時後，我們決定把 pD 改成 __int128 試試看，雖然題目保證答案不超過 $$ (一開始想說 long long 應該就夠了)。

$$

AC 後反而一臉矇逼？！

pH 雖然噁心，但是看起來是目前比較有機會做出來的題目，因此為了判斷 pH 的線段相交，我們從 Codebook 抄了將近 $$ 行的模板，但是寫一寫就半放棄了，實作好噁心。

pE 可以發現對於一個連通塊 (高度相同) 他們的 spawn 值必定相同，並且一個點如果可以是 spawn 點，那麼該連通塊上所有高度比他小的的鄰居必須全部都是 spawn 點。
因此我刻了 DSU 來維護連通塊，再對高度做排序，由低往高枚舉，實作起來其實蠻乾淨的。

$$

耶，一發 AC！我們的排名也回到第 $$ 名，第 $$ 名跟我們 penalty 差不到 $$ 分鐘。

這時候差不多封板了，pB 跟 pH 蠻多隊寫出來。

pB 我寫了從後面回推的 greedy，但很快被隊友發現是假解。後來林立上提出另一個 greedy，從對答案的貢獻下手。我們用這個方法試了範例測資都是對的，所以就跑去寫寫看。

$$

林立上 orz，想不到這樣就過了，難怪那麼多組比我們早寫出來，賽後題解出來也被證實這是一道水題，完全是我們想得太複雜了 (其實是古老 ABC round 的題目直接搬過來的)

剩下的時間就都拿去寫 pH 了，雖然範測有過，但是送出去後吃 WA 也沒有頭緒。賽後推測可能是因為 $$ 然後內積和外積都有乘法所以有可能會 overflow。

結果

AC：$$
penalty：$$
Rank $$

結果 pF 真的是 flow，但要用到我還不會的 Konig’s Theorem。

開板後維持在 Rank $$，第 $$ 名的 penalty 只多我們 $$ 分鐘，不過在開板前大概就有猜到可以晉級，因為後面沒有 $$ 題的。

接下來 10/15 就要打 NCPC 決賽了，希望中間這段時間可以多 virtual 個幾場 (如果 NCPC 決賽不幸燒雞還有 TOPC 可以打)。