【World Finals 團練紀錄】2020 ICPC WF Moscow Invitational Contest
簡介
The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。
隊伍組成
National Taiwan University, Team 8BQube
蔡旻諺（baluteshih）
蘇柏瑄（briansu）
鄭忠宜（icube）
不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷
前言
這場是 2020 給不能到現場的隊伍打的線上邀請賽，因為畢竟跟 WF 有點關係就想說拿來當作正式的 WF 打打看，不過打起來題目風格感覺上是差不少，雖然好像不能當作這場打差的理由就是（
目標：打出一場沒有遺憾的 World Finals！
成果
時間：2024/3/11 11:20~16:20
$\color{green}{A}$ $\color{red}B$ $\color{gray}C$ $\color{gray}D$ $\color{green}E$ $\color{gray}F$ $\color{gray}G$ $\color{green}H$ $\color{gray}I$ $\color{gray}J$ $\color{green}K$ $\color{green}L$ $\color{green}M$
Penalty：869
Rank(versus official)：10
這次除了一樣規定過兩小時多時要有人看完所有題目外、新增了一項我要在夠早的時機點去看幾何題，才可以在閒暇之餘想實作。
開場題目翻一翻就發現不少題目敘述都很短，超不 WF，然後馬上就被 CF 作弊人劇透 E 是水題，但一翻就發現他是題目最短的，姑且先看完，雖然確實是水但還是跟蘇柏瑄討論一下做法，而他看起來想得比我快、包含細節，所以就交給他寫。
他寫之前先跟我講了 B 的題敘，是個感覺好好維護就會做完的資結題，但暫時沒直接的想法。
我繼續往後看題目，看了 F 完全看不懂，看到 H 發現是水題，但是 parsing 所以又是蘇柏瑄的題，但蘇柏瑄不知道為什麼還沒寫完，根據計分板速度其實好像應該要寫完了（？
這時候 icube 跟我講 L，一個感覺蠻經典吃東西變胖圖論題，不過一時間沒什麼想法，這時候蘇柏瑄 pE 過了
--pE AC 0/13
我看了下計分板果然有人過 H，就跟他講完 H 後讓他繼續寫。
我接著看到 I，感覺應該要是不難的幾何互動題，但好像又有不少細節要思考就先放著。
這時候 icube 繼續跟我講 M，打牌把玩題，但我超不擅長這種題所以我聽完也只能放著，先在 B 跟 L 之間來回交換想，但 L 我一開始收到的題敘是錯的，所以完全沒想法，B 則是第一瞬間就先往蓋類似答案樹的方向去想，所以先想到了做類似最小生成樹的東西，可能 boruvka 會很有幫助，但後面有一個偏序想不太清楚。
蘇柏瑄寫完 H 後
--pH AC 0/24
看計分板是有人過 L 了，就先跟蘇柏瑄講 L 的題目，講到一半重讀一遍題敘發現之前收到的題目錯了，就瞬間產生一個樹 dp 搭配 greedy 合併的做法，直接讓蘇柏瑄開寫。
此時一旁我在獨自思考 B，想到一半看個計分板發現 BKM 都有人過，icube 就跟我說 K 的題目。K 第一瞬間聽完就覺得要 2^k 窮舉那些加刪邊操作，但刪邊的想不清楚，我就邊把我的想法念出來給 icube 聽來理清自己的思緒，唸一唸就差不多會做了，雖然中途修正了一下但最後還是得到了做法。
這個過程其實蠻久的（還包含 wiwiho 外送的午餐到了，感謝 wiwiho 幫忙），等到蘇柏瑄寫完後已經過一小時多了，結果傳上去
--pL WA
他一時不知道錯什麼，就印 code 後先去旁邊吃飯換我寫 K。
我寫到一半蘇柏瑄就跟我說那個解假到不行，完全沒想到可以先拿一個葉子後回來根再去別的葉子，做法綜合起來就是很可能是一直拿葉子。但問題就是題敘一開始給的 1 號點根本是假資訊，所以這是一個無根樹的題目，導致一時間我們直接不會做，只能放著。
icube 說等等有空的時候寫個 M 的 checker，他有點想法。
等到我 K 寫完之後自己測了一下確認沒問題
--pK AC 0/107
我們就開始陷入苦思，當然因為沒事做所以在寫 M 的 checker，不過寫完之後暫時也沒事做就讓 icube 開始玩 M。
過一陣子我去上個廁所突然就想到搞不好是 greedy 拔葉子，就嘗試說服蘇柏瑄後讓他打斷 icube 開始寫，結果寫完多測一點測資蘇柏瑄就構出大反例把我 hack 掉，這之後我們兩個都不太知道怎麼辦，想了很久，看了一下計分板後發現 A 有人過蘇柏瑄就跟我講題目。
icube 在被打斷的期間表示他看完所有題目了，其中包括我之前看不懂的 F，聽完就知道這題精神上很簡單，但是要積分，很煩，有空才會寫。
A 就是個煩躁方塊題，naive 做顯然不行，一開始我還以為是要估 <=7 的方塊種類數，但根本就直接用總數量 bound 住好好 bfs 就好了，就跟蘇柏瑄講這個做法，大概晚點就可以寫。
L 到後來還是沒什麼想法，一旁的蘇柏瑄嚷嚷著要不要直接對某個東西排序 greedy 傳傳看，但我還是證不出來他是對的還是錯的。不過 icube 倒是成功試岀 M 穩定過的做法了，一傳
--pM AC 0/184
赫然發現剩兩小時了，可怕。斟酌了一陣子後，決定亂傳個 L 看看，這個都沒過應該就別想拔葉子了。
--pL WA
果然 WA 了，所以這題直接被我們丟棄，蘇柏瑄就開寫 A，我繼續想 B。
計分板顯示 D 也可以做，就讓 icube 花時間想一下。他是有看出一些 D 的規律，但很難拿來做整題，只能做一個感覺用處未知的給編號算座標而已，我自己 B 則是怎麼想都逃不掉三個 log，基本上是不可能過。但多想一陣子就突然覺得好像壓掉一個 log 了，就跟蘇柏瑄說等等寫 B
等到蘇柏瑄 A 寫完後
--pA AC 0/230
我就上去寫 B，結果寫到一半我就發現自己假了，修不好，問了蘇柏瑄這能不能修他也覺得很難，這時候應該剩最後的一小時，所以我們勢必要在 BDL 之間選擇題目，看了計分板後可能可以考慮 J，但蘇柏瑄聽完題說這不行。
B 感覺是有機會做出來的，L 其實也應該可以再撿回來試試，畢竟這題很快就被開掉，搞不好那時候想到就瞬間寫完。
D 則是全靠 icube 了，所以後期的策略大概就固定在這樣。
經過一陣子思考後，我突然想到直接對最大生成樹的邊由邊權小到大窮舉的方向，發現其實一條邊被窮舉到時，他一定是兩側選一邊全吃，這時候就有一個乾淨的妙解冒出來了，趕緊跟蘇柏瑄分享後就讓他開始著手改，我全力押 B。
等到他寫完之後上傳
--pL AC 2/271
我們就抓緊最後的時間把 B 肝完，我因為有神秘的 boruvka + 答案樹信仰（主要也是因為如果要換做法大概沒救了）就先把這個框架該刻的刻完，刻到一半蘇柏瑄就說能不能只維護環上相鄰的點對，我第一直覺其實覺得套在我這個做法上會漏資訊，但基於沒別條路了、這又是一個關鍵性質，糾結了一下還是開始寫。
到後來其實壓在最後五分鐘左右寫完，但 CE 抓超久，終於修好後測了一下傳上去
--pB WA
馬上就發現自己有白痴地方寫錯，改完再傳
--pB WA
然後就在不知道什麼錯的情況下結束了。
結語
1. 終於有一個 virtual 沒牌（？），但這場有蘇柏瑄退化 debuff＋運氣不好假解卡太久，希望正賽運氣夠好沒遇到這種情況，我們大概還是有機會的。
2. B 後來發現是假解，但那個關鍵性質其實很好用，多想一下就發現利用這個性質可以直接維護題目要的東西，不用蓋答案樹了，大概如果當時多一小時是肯定做得出來。
3. F 到後來也沒時間寫，整體來說還是 L 假解太傷啊...
4. 不過後來討論有意識到另一個問題是蘇柏瑄寫 code 明顯慢很多，開始工作後寫 code 可能越來越悠閒了，因為不太好，就建議他要不要乾脆有空找時間單刷 gym 三星場，反正題目簡單沒壓力、隨時中離又沒差（反正我們也練不到那些）。
5. 承上，其實我感覺現在重點已經不是做題或是實作能力，而是比賽時的寫程式的穩定度和速度了，這個我之前看東大的選手有人一直在開經典題比賽練習能刷多快，我就在懷疑搞不好這真的是賽前最好的練習手法，畢竟這段時間內要變聰明、變厲害也難，不如讓自己已經有的技巧能夠更加熟練又快速的發揮出來，才有更多時間可以做難題，也有空間容錯。
6. 我自己大概也需要這種練習，畢竟我開賽時需要一段時間進入狀況，但如果長期保持在比賽狀態，這段時間能夠縮短（之前有一次一個禮拜打六場有感）。
7. 不過實際比賽大概還是看運氣，就來賭賭看正式賽願不願意讓我們拿牌吧XD
8BQube 加油！
留言
張貼留言