【心得】2022 ICPC Asia Taoyuan Regional 心得

11/19

這次比賽的地點在桃園的武漢國中，蠻偏僻的，但是裡面冷氣超涼。我們的座位後面是零食區和廁所，旁邊是點心區，超方便。今年的衣服是粉紅色的，材質穿起來很透氣舒服，背包看起來也不錯 (聽說某年的背包背一下子就壞掉了)。
今天主要是 測機X 認親大會O，還被別校同學採訪 (然後我們就直接推薦小褲褲那隊 hehe)。有趣的事情是有工作人員看到我們的隊名問我們隊是不是有吳邦寧，看來是隊名取的太毒瘤了。
上次原本打完 NCPC 決賽說要多練幾場的，結果因為期中接踵而來，根本沒時間練習。將近一整個月沒碰競程，昨天跑去 virtual 去年 Regional 的題目，結果只寫了三題就跑去睡覺了，超諧。今年台大報了 $14$ 隊，交大報了 $10$ 隊，清大 $7$ 隊，希望明天不要燒雞。

11/20 比賽

開場我先打 vimrc 和 default code，隊友讀題目。過了不久，林立上就把 pM 丟給我了，是 DSU 的裸題。我馬上打好然後送出。

$\text{[0:06] pM }\color{red}{\text{WA}}$

傻眼，我笨到連 DSU 都不會刻了嗎？後來發現原來他題目的範圍給錯，前面寫 0-based 後面寫 1-based。改了一下之後就 AC 了。

$\text{[0:09] pM }\color{green}{\text{AC}}$

就這樣莫名其妙被坑了一個 penalty ==。pC 也是水題，求逆序數對的數量，然後 $N \leq 100$。我就直接寫了最簡單的 Bubble Sort。

$\text{[0:13] pC }\color{green}{\text{AC}}$

這時候我們又開了兩題，pA 很水，但是打表要花一段時間。pG 是很水的字串匹配題，暴力就可以過了，所以我就先去把 pG 寫掉。

$\text{[0:27] pG }\color{green}{\text{AC}}$

接著我回去抄 pA 的表，打了好久終於打完了，測了一下範測有過就直接丟了。

$\text{[0:35] pA }\color{red}{\text{WA}}$

應該是打錯表了，我請林立上幫忙檢查，我去讀其他題目。結果原來我把 C 跟 G 看反，然後範測又剛好沒有這個 case，改好之後再丟一次。

$\text{[0:39] pA }\color{green}{\text{AC}}$

這時候記分板上面都跟我們一樣 $4$ 題，這代表我們要去開新的題目。pB 是數學題，pD 是閱讀題，pJ 跟 pF 是實作題。這些是看起來比較可做的，我也不知道哪來的自信先去做數學題。做完之後就直接丟，很顯然我的唬爛解是不可能會過的。

$\text{[0:57] pB }\color{red}{\text{WA}}$

這時候隊友說 pD 好像暴力做 $O(N^2)$ 就會過了，然後我看到那個 $N \leq 10000$ 就有點怕，不過測機的時候 judge $1$ 秒大改可以跑 $5e8$，然後這題開三秒，應該沒問題。所以就先把 pD 給游承桓做，我繼續推 pB 的公式。

$\text{[1:16] pD }\color{red}{\text{WA}}$

吃 WA 了，debug 把過程印出來後發現題目附的圖跟說明不符合，於是林立上就送了 Clarification 去問，結果真的是畫錯了。後來 debug 發現是改了寫法後有個地方沒有更改到，修改完後就 AC 了。

$\text{[2:35] pD }\color{green}{\text{AC}}$

到這邊我們剛好第 $30$ 名，在銀牌線上。pJ 蠻水的可是實作的 case 超多，pB 公式還沒推出來，所以我就去寫 pJ。因為會用到線段樹我就開始打開 Codebook 抄，被游承桓說我用的 zkw 線段樹左閉右開區間很毒瘤。我們一邊判 case，林立上繼續想 pB。

$\text{[3:38] pJ }\color{red}{\text{WA}}$

case 應該都有判到，所以我判斷是查詢的區間寫爛了。果真我有個地方忘記 $+1$。

$\text{[3:50] pJ }\color{red}{\text{WA}}$

又有地方忘記 $+1$，好粗心，改完之後就 AC 了。

$\text{[3:57] pJ }\color{green}{\text{AC}}$

這時候我們排名大概在 $26$ 附近，要穩銀牌一定要做出 pB。
pB 我們卡在：數 $N$ 個點圍成一圈，每個點塗上 $K$ 種顏色的其中一種，求相鄰點顏色不相同的方法數有幾種？後來打算用排容，發現剛好會形成等比級數，打好之後過了範測，又測了小 case 沒問題後就丟了。

$\text{[4:32] pB }\color{green}{\text{AC}}$

AC 了超開心，剩下的時間應該也不夠再寫出一題了，所以就跑去旁邊的點心區拿東西吃。

結果

AC：$7/13$
penalty：$872$
Rank $25$

第 $24$ 名也是清大的隊伍，但我們的 penalty 太高了，下次要再細心一點。
這次清大成績 $2$ 金 $2$ 銀 $2$ 銅，超棒！
大一上學期的競程之旅應該就到這邊了，接下來要繼續被考試轟炸到期末了。寒假有時間的話多練習，看能不能拚個金牌。

喔然後不要亂立 flag。