ICPC World Finals 2025 正式比賽紀錄

前言

這篇文章是以我自己的視角所撰寫的 49th ICPC World Finals 的正式比賽紀錄，所以裡面當然會有這場比賽的題目與爆雷。如果你認為自己未來進 World Finals 的機率 $> \varepsilon$ 的話最好最好迴避一下。

另外，這篇的撰寫時間是比賽後的四個月後，可能有些小細節與實際不一樣但我相信大的比賽走向還是正確的。

=== 防雷線 ===

正式比賽紀錄

比賽開始後我就先打完 default code 跟設定好環境，弄完之後還沒有人過題，就從 E 開始往後看，看了一下發現沒到很懂，過了沒多久之後 L 有人過了就趕快請 syl 讀一下題，我繼續往後看 F。

F：「有 $n$ 隻貓咪跟 $m$ 種植物，每隻貓咪都有喜歡的一個植物種類集合。現在你要將這些植物排成一排，不能有重複的植物，接下來每隻貓咪會從左到右看過一遍植物，若現在的植物是牠喜歡的那牠就會停下來，否則會繼續往右看。現在給定你想要讓每隻貓咪停在哪一個位置，問存不存在一種排法滿足這個條件。」

讀完感覺是簡單題，但感覺很 greedy 好像不是我的題，但總之先放著等等想，接著我就被丟了 L。

L：「二維平面上有 $n$ 塊長方形的區域是陰影，你可以往上下左右移動，若你在非陰影處且往下走一單位的話會花費 1，其他都不會有花費，問從一個點到另一個點的最小花費。」

反正只能往左右走都不會有花費所以可以直接把 x 軸的維度丟掉變成一維線段，然後把線段取一下聯集就可以直接算了。我就直接上去寫了一下，寫完有一筆範測一直輸出錯我看了很久又沒找到錯就又問了一次 syl 題目，然後才發現原來往上走不會算，有點笨，改完就過範測了。

[0:17] pL AC

過了之後就看到他們兩個在討論 D 然後仲準備要上來寫，看了一下計分板發現 F 也被開掉了，我就先自己稍微想一下，想了一下沒啥想法，不知道要用什麼順序 greedy 才是好的，後來沒多久後 I 被開了我就問了一下題目。

I：「互動題。有一台有 $n$ 個格子的角子機，一共有 $n$ 種可能的圖案。你的目標是讓所有格子都出現一樣的圖案，你能做的操作是挑一個格子並轉動任意多格，轉動完後 judge 會告訴你目前顯示的格子有幾種相異的圖案。在 10000 步以內完成目標。 $n \leq 50$ 。」

問了一下 syl 目前的想法覺得他應該可以自己做完所以我就繼續對著 F 乾燒。

乾燒了很久之後仲寫完 D 了然後傳。

[0:41] pD WA

一上傳之後我就馬上把 F 丟給他因為我覺得我沒救了，但講完題目之後就看到 D 冒出一個 WA，然後他就先回去 debug 了。後來過了一下就找到 bug 然後傳。

[0:45] pD AC

現在板上有被開的就是 FIJ 這三題，F 仲聽完題目想了一下就提出了一個作法，但那個作法暴力做會是 $O(n^2)$ ，可能還要再優化一下，然後他可能覺得我可以優化下去就把這題還給我然後自己去做 J。有了這個想法我自己又再多想了一下總覺得要走下去有點難就把它丟了，過不久後我終於好像想到了一個作法，但實作有點小麻煩，反正現在沒人在用電腦我就直接上去寫了。

但在寫的時候我就一直自我懷疑這到底是不是對的，因為據我所知這個作法不太好寫，感覺不太可能那麼多人都寫那麼快，總之我就一邊寫一邊懷疑，然後寫到一半忽然不確定一個部份是不是好的，剛好這時候聽到隊友會 J 了就先把電腦讓給他們我先下機想一下。

在下機的時候 syl 會 I 了就順便幫他驗一下，聽起來很合理。我又想了一下 F 感覺應該要是合理的，但心中主要還是被「為什麼其他人可以做那麼快」影響，總之就等等接在 J 後面寫完吧。

過沒多久之後 J 寫完但範測 WA 了，發現是漏了一個 special case，仲就先下機我先嘗試改一下，但在寫的時候我的心中想的還是：

我有沒有想錯，為什麼其他人可以寫那麼快
這個好難寫，WA 的話怎麼辦
這真的是好的嗎？會不會其實我想錯了

總總的負面情緒讓我根本沒有辦法好好寫，上機的那段時間是非常痛苦與崩潰的，所以在聽到隊友 J 修完了之後我就說我崩潰了要下來，然後說我還是不確定我的解是不是好的，然後仲問我要不要去想其他題目我看了一下板發現 K 剛剛被開掉就轉去想那題。

K：「題目有點抽象不知道怎麼好好解釋，先跳過」

問完題目簡單討論一下之後仲就把 J 修好了

[1:17] pJ AC

之後 syl 上去寫 I，仲回去拯救被我搞爛的 F。剛剛跟 syl 問 K 的題目的時候他說他想要猜說一塊 1*1 是好的 iff 左上角+右下角跟左下角+右上角相同，因為中心點要滿足這個條件。感覺是有道理的，然後我就手算了一下發現對角線的數值是好的，這樣就代表整塊都是好的吧。

在想的時候仲就把 F 修好了，他說只要好好優化他前面提過的 $O(n^2)$ 就好了。

後來再多想一下 K，感覺把式子移項之後會變成這題，座標 $(i, j)$ 的高度可以表示成 $a_i + b_j$ ，所以把變數當成圖的點，那些高度限制就會是兩個點的總和必須要是多少，且 $\min(a) + \min(b)$ 要非負，這樣的限制下要最小化兩個點的總和。反正很自然的可以把每個 cc 先處理完，然後因為圖是二分圖，所以對每個 cc 可以決定一個變數 $x_i$ ，然後這個 cc 影響到的 $\min(a)$ 就會是 $v_i + x_i$ ，影響到的 $\min(b)$ 就會是 $u_i - x_i$ ，然後感覺會想要讓每個 cc 的值平均一點，再套個二分搜可能就做完了？感覺還有點細節沒處理好。

想到這裡的時候差不多隊友已經把 FI 都弄完了，印象中好像 I 好像 WA 範測之後有先上去寫一下 F，F 寫完才又上去改，所以過的時間差不多。

[1:56] pF AC
[1:58] pI AC

接下來就是 K 有沒有單調性的問題，把現在的想法跟隊友說之後他們覺得應該要有，但我其實還沒確定平均配是不是好的，但總之反正不難寫就先上去寫一下。然後在上去寫之前就被仲叫住說應該是要讓每個 cc 影響到的 $\min(a)$ 一樣，因為每個 cc 影響到的 $\min(a) + \min(b)$ 貢獻是一樣的。

合理至極，然後我就直接上去寫了。寫的過程蠻順的但寫完之後 WA 範測，稍微 debug 一下發現好像沒有單調性不能二分搜。

：欸這個好像沒有單調性欸
：怎麼可能

但對，我也想說怎麼可能，但我覺得我沒有寫爛就先讓仲寫已經做完的 H，然後下機重新推一次發現那筆範測真的沒有單調性。好吧，重新想一下。

然後就發現我根本只在乎至多兩塊 cc 的值阿，也就是我只在乎某塊 cc 最多可以減少多少，然後判點 case 就做完了。想完之後再重新驗一次感覺超級合理，反正就接在仲後面寫 H，然後還有點時間就順便幫 syl 驗一下 A，感覺一樣是合理的但我對這種 greedy 題不太有把握就是了。

總之後來仲 H 傳了

[2:45] pH WA

我就先上去把 K 修好

[2:53] pK AC

感覺心態回來了一點點，但感覺跟平常還是差很多就是了。

這時就 syl 上去寫 A，然後我幫仲驗一下 H。

H：「給定 $m$ 跟 $n$ 個數字，定義一個正整數是好的若它 $\leq m$ 且可以用那些數字湊出來（無限背包），對於 $0 \leq d \leq 8$ 輸出好數字們總共有幾個 digit $d$ ，6 跟 9 視為相同的。」

聽完題目跟想法後感覺沒啥道理錯，所以就開始黃色小鴨，然後黃色小鴨到一半仲就自己發現他一個地方寫錯了，看完一遍之後我感覺只有那裡錯，但反正我們 penalty 已經爆炸的徹底了就直接上去改完傳了。

[3:02] pH AC

然後我就稍微了解了一下現在的情況：B SPb 53 分鐘就過了，但現在還只有兩隊，有點抽象，E 有一些隊過，C 沒看但現在沒啥人傳，G 是幾何然後現在還沒人過就代表可以丟了，所以看起來剩下時間就是專攻 BE 兩題吧。

E 再重新讀了一遍題目終於看懂了。

E：「考慮一張二分圖，左邊 $n$ 個點右邊 $n$ 個點，定義一個 pair $(i, j)$ 是好的 iff 從(左邊 $i$ 的點或右邊 $i$ 的點)走的到(左邊 $j$ 的點或右邊 $j$ 的點)，現在支援 $m$ 次加邊操作，每次操作後輸出有幾個 pair 是好的。」

讀完之後發現 A syl 寫完了

[3:10] pA AC

看了一下發現我們回到牌線了，wow

總之現在的目標就是要想辦法開出兩題，因為我們 penalty 非常慘烈所以要拿牌必須要開兩題，在目前還有兩個小時的情況下只開一題一定不夠，所以就回到我們後期常用的打法：仲一個人做 B 我跟 syl 做 E。

E 想了想感覺就很啟發式合併然後要判點 case，syl 提出了個 bitset 的想法，不知道 $O(n^2/64)$ 會不會過但好像還要多乘一個 log，有點寄。

後來我們兩邊都乾燒了很久，仲有上機打了一下 B 的表但好像沒看出了什麼。後來很快就封板了但兩邊都沒什麼進度，仲就回來跟著我們想 E 然後他想沒多久就發現啟發式合併直接硬維護另一邊複雜度就是好的，但我跟 syl 那時候都聽不太懂所以他就自己上去寫掉了。

[4:??] pE WA

WA 了之後我就上去寫了對拍

[4:38] pE AC

後面我就是盯著 B 發呆，完全沒有半點想法，而且感覺我對這場比賽的心態已經完全炸裂了，只想要快點結束。後來接近賽末的時候 syl 亂提出了一個解，雖然覺得一定是錯的但還是嘗試在比賽結束前寫完，但失敗了，比賽就結束了。

後話

這裡也打一些後話，畢竟外面那篇需要防雷沒辦法全部講。

感覺這整場我自己完全就是被 F 弄到心態沒了，但現在回想起來我也不知道為什麼自己當時會撿著這題很 greedy 的題做那麼久，我自己最不擅長也最討厭做的題型就是 greedy，然後平常我遇到也確實會稍微想一下就丟給隊友，像是幾個月前的 APAC 就是這樣。如果我那時候想一下就直接跟 syl 交換題目變成我做 I 他做 F 或許今天結果就大不同了，但搞不好我變成卡 I，誰知道。

另外還有一點就是我完全被計分板影響了，我在想的時候看到很多隊都很快就過就一直覺得有很簡單的作法，導致想到一個複雜的作法之後反而不相信自己解的正確性，變成只是讓自己心態越來越糟。現在再重新回想一遍我賽中的那個作法我覺得該是對的，但那時候就嚴重被其他隊影響到而讓自己越寫越崩潰。不過這也怪不了別人，畢竟自己 ICPC 都已經打三年了，還會被計分板影響心態只能是自己的問題。不過說真的，在正式賽中感受到計分板帶來的這麼大的絕望感也是第一次就是了。

不過其實我們中期有救回來且理論上是有充裕的時間同時做 BE 兩題，但偏偏我們後期習慣的配置是仲一個人做一題我跟 syl 做一題，所以這裡很正常的就會讓仲去做 B 我們兩個做 E。但偏偏吧，B 是一題很梗的題目，梗題通常越多人去做越容易做出來，如果我沒記錯作法的話這題要用兩種不同的方向去看題目才能解出來，所以要一人打穿這題是非常難的。我到現在還是相信如果那時候是 syl 跟仲一起做 B 的話 B 就做的出來，畢竟賽末 syl 提出的作法是跟仲想的不同方向的，就算那是錯的但只要讓仲知道有這個方向應該還是會增加不少做出來的機率，只能說，後期沒救回來某方面也是我們的策略被題型卡了吧。當然也是我們不夠聰明，只要我或 syl 早早想到 E 的解就可以更早三個人同時想 B，但不知道，我那時候真的被 F 搞到沒什麼信心好好參加比賽了= ="

我從高中打競程以來一直覺得自己是一個實作能力遠大於思維能力的人，這也不是因為我實作多厲害，反而是我的想題能力太差了，然後我自己也不怎麼喜歡想同一題想很久，造成了我思維能力這一兩年感覺沒什麼成長。確定進 WF 之後我們先練了幾年 WF 古題，然後發現 WF 的題目多數都沒有什麼思維成份且比較無聊一點，很大一部份是在比誰實作比較穩，而且幾何好像很重要，那時我有發現我自己實作好像沒有想像中穩定，再加上我們隊上已經有一個紅黑人的大腦了所以準備的大多數時間我都在練實作跟幾何，反而沒有什麼顧思維。但我那時候覺得自己練實作有點練到麻痹了，反而變得沒有感受到解題的樂趣，有點越來越討厭的感覺。

結果今年的題目嘛…，反而比較重思維而沒有什麼實作，而且唯一的幾何題還是很難的題目（而且聽說幾何成份也不大），有點捉弄人的感覺。不過至少今年的題目就蠻迎合現代題風的，沒有出一些太經典的問題或純考實作，可能也代表他們正在轉型吧，至少算是件好事。但是吧，我感覺自己辛苦練的大實作和幾何沒有派上用場，整理的 codebook 甚至比賽中完全沒有翻過，還是覺得蠻難過的。

雖然我很不喜歡比賽打爛之後在抱怨題目，但我還是想要抱怨一下這套題的難度配置，出場看直播看到他們說 H 是 “to get better medal” 的題直接笑出來，鬼才信，然後雖然 E 不是我想的，但感覺看這 AC 數說是銀牌題也有點牽強了，這場比賽如果放在一場 regional 或甚至是 championship 應該都會是不錯的比賽，但放在 WF 就有點簡單題太多，4-17 名全部都九題實在是看起來很好笑。不過再怎樣這份題單都比去年 WF 出的好了，那年真的不知道在出三小。

不管怎樣，雖然打爛的主因是我前期被 F 搞到沒心態了，但我覺得有一部份是我們的運氣真的糟透了。