ICPC World Finals @Luxor 世界總決賽紀錄

部落格快要長草了趕快趁現在更新一下，也是為了把自己花這麼多時間投入的活動做個好好紀錄。
如果是怕暴雷題目的，需要跳過的段落是「正賽」與「賽後與心得」兩段，包含賽後心得裡面的 comment。

前言

在大一IOI結束後ot和olmrgcsi邀請我同隊，暑假就組成ckiseki開始團練。ckiseki 這個隊名應該是由他們前一個隊伍的名字 kiseki 改過來的，我們三個人其中一個共通點是都是建中的，所以前頭加了一個 c 湊成 ck 的縮寫（？）總之我們那時候練得蠻多的，在當年（2021）的下半年在臺北站用線段樹和一些壓常得到了 46th world final 門票。本來預定應該是 2022 比賽的，但因為 covid 的關係延後得遙遙無期，直到 2023 年初才得到會在 11 月去 SSH，結果因為以巴問題又延期，2024 的 1 月才得知 2024 年 4 月改在 Luxor 舉辦。如果是大四才拿到票的學生，可能都已經工作兩三年了，可以說非常消磨熱情。
我們隊在進 wf 後參加了三次的ptz camp兩次的ocpc，以及很多的 universal cup。雖然感覺我們是有成長的，但越接近 final 越發現前排隊伍有點太過耀眼。如果我們跟以前的隊伍比的話，看排行榜有機會是可以拿到銀牌，但本次比賽的隊伍名單一字排開大概十隊有紅黑人，再把一些平常團練打得很好的隊伍算進去的話，悲觀一點連拿牌都很難，如果看我們 ucup 的成績大概有一半是超級拉垮的。不過賽前一個禮拜 vir 某場 WF 的時候看到東大也是最近 vir 的而且跟我們同題數只輸 5 分鐘罰時，雖然大概是他們太老導致很少練但還是讓我稍微感到樂觀一點，努力帶著這種樂觀啟程。

啟程

結束落落長的前言，開始本次旅遊的流水帳。

往 Luxor 的旅程從桃機開始，週六的晚上十一點的飛機，我們七個人包含教授在櫃檯集合並登機；在同一個櫃檯也已經看到交大清大他們。這是我第一次搭日本或台灣以外的航空公司（阿聯酋航空，回來台灣之後學習到我是第一次坐所謂 A380），有點開眼界的感覺，經濟艙的座位上竟然有萬用插座（雖然九小時應該非常需要xd），而且還有一個被擋住的樓梯，往上層艙看起來有一個像是酒吧的東西；他們的餐點也還不錯吃。飛到杜拜的飛機坐得很滿，而且我們是半夜起飛，所以大家都在睡覺，我原本帶書來看但我也不好意思在他把機上燈光關掉的時侯開自己的座位燈xd。

坐在中間的位子蠻難睡的，努力消磨時間跟睡覺總算到達杜拜，是當地凌晨五點。到杜拜又是另一種開眼界，我們還待在轉乘的區域可以逛的商店就已經非常多，有很多的精品店還有偶爾會遇到emirates的周邊商品店。這裡已經可以遇到很多來 icpc 的人了，我們在杜拜的麥當勞買了一個約五美元的大薯四個人分著吃（好貴），剛好對面坐 NUS 的 coach；回到登機口之後還有澳洲跟日本的東工大跟京大的樣子，不過我幾乎不敢搭話，而且不知道是吃太飽還是吃壞肚子，有點肚子痛再加上很累不太能專心。

杜拜到開羅的飛機上我終於打開我筆電上預先載好的 mygo 來看。在起飛前聽說伊朗又跟以色列開打，我看確實飛機的航線就往下彎不通過以色列。入境後我們需要扛著行李移動到另一個航廈，十二點的氣溫大概是 26 度，沒有想像中熱。國內線的安檢反而更加頻繁，我們在到埃及航空櫃檯前過了一個關卡（有分男女，而且不知道標示在哪裡很酷），然後登機口前又過了一個，而且都會摸一次全身檢查。在埃及航空的櫃檯看到更多人了，包含東大的 yutaka 他們還有 stanford 的一些人。最後從開羅到 Luxor 搭埃及航空，他們的起飛和降落非常可怕，幸好一小時就到了。

度假

Day 0

抵達 Luxor 後才知道剛剛就在我們後面的交大和 NUS 有人被卡在開羅，真是多災多難。跟著上大會提供的接駁車後我就在巴士上小睡了一下。
到達的飯店是尼羅河島中的一個像是度假村 jolie ville，我們數台遊覽車的人擠進櫃檯可以說非常混亂。這裡蠻大的，居住的區域是一個一個的多邊形，每個多邊形是一圈的房間；我們一隊住的地方是兩個互通的房間，一間放了一張雙人床，隔壁則是兩張單人床，看起來非常寬敞。房間裡放好了兩整大箱的瓶裝水，看起來不用擔心渴死了。
真正坐下來休息大約是週一的下午。感受到什麼叫做風塵僕僕，洗了個澡之後，我們逛了一下整個 jolie ville，到處都是 icpc 的牌子，並且還有官方提供的 chill zone，有大型 connect four、拉密、桌子足球、飛碟球、西洋棋還有桌球。周老師終於得償所願打到桌球，但在河邊的室外風超級大，而且太陽也很刺眼，根本沒辦法好好打XD。

似乎落地之後我的肚子痛就解除了，可喜可賀。晚上的行程表是 welcome dinner 加上 team registration，我們這隊的 registration 時間是比較晚的九點，於是就悠哉的在餐廳吃完晚餐之後回房間休息，結果我果然在房間開始大爆睡（畢竟下午又死不睡跑去逛街），要不是 ot 把我們叫醒可能還會遲到更久。總之就是跟著 coach 去「Nile Hall」開始跑十個櫃台，繳交一些文件以及比賽當天要放桌上的 codebook 跟文具，還有領取一大堆的紀念品、文件，以及每人三件的 T-shirt。這個 T-shirt 的字跟底的顏色是我們自己選的，但太久以前導致我們幾乎都忘記是什麼顏色了XD。回去之後繼續我的大爆睡，順帶一提我佔走的是那張雙人床，抱著我的軟軟owo。

Day 1

隔天的行程是去 karnak 神廟的 excursion，我們一大群人從 jolie ville 裡面分批搭上船，稍微欣賞一下尼羅河美景。
跟我們同一艘船的有馬里蘭大學南京大學還有偶像（？）東工大，不過船開的時候聲音蠻大的，不知道是導遊還是開船的人又把非常埃及的爆音音樂開得很大聲所以我其實隔一個人的聲音就聽不太到了。一開船我的帽子就差一點被河上的強風吹走，接著因為我坐在船頭的位子，船加速之後前面的水花就開始會濺到我，只好用書包稍微擋一下。導遊是一個感覺四五十歲的婦人，稍微介紹了河岸兩邊的東西之後我們就接近上岸了。上岸後又接著跑去搭遊覽車xd，似乎不知道為什麼我們今天 excursion 的分組就是上了同一艘船就是同一組了，導遊問我們這組的名字要叫 future 還是 lamesis，沒有人知道怎麼回答不過傅老師就幫我們這一團決定就叫 future xd。我們在等遊覽車的時候後面的南京大學突然就有人在說「你是不是開始想回飯店玩原神啦」超級好笑。

下車抵達 karnak 神廟的入口後，導遊讓我們先去廁所，一到廁所前才知道還得收錢的？一美元可以給三個人進去上，但裡面也不是說特別厲害。聽到後面的中國人真的會說美刀覺得很稀奇。接著就把入場票發給大家進去，然後是熟悉的安檢環節。進去之後導遊就邊介紹邊帶著我們向內走，一走出室外就感受到埃及好熱，確實乾的熱是比溼的熱舒服一點，但彷彿會真的熱暈你，許多人都戴上了帽子。
在這個神聖的神廟裡 ot 抓到時機跟東工大他們搭話，然後我也趁機跟著上去貼臉成功要到 tatyam 的合照，因為語彙力不足不知道該說什麼跟對方是什麼意思但不知道為什麼就握手了？？？我有一種簡直是偶像見面會突然握到手的感覺，這好微妙xd。然後過了一陣子才想到說沒找 noshi 合照是不是失禮的一種。

導遊講解完並帶我們走到深處之後我們有自由時間十五分鐘，去紀念品店逛了一下買了汽水喝。上車回去之前我們順便領取了 lunch box，lunch box 的領取是蠻混亂的，他會問我們之前填的口味是什麼，但我印象中官網的 survey 只有問後面三天的午餐盒而已。我就跟著前面的人講了 chicken，總之領取到餐盒之後趕快上車。我們直接就搭遊覽車回到飯店（沒有經過船），今天的導遊也在這時跟我們道別，他直接在一個 Y 字路口的正中心下車有夠狂XD。
回到飯店後才有辦法好好吃 lunch box，其實不太好吃（伏筆）。
雙人床上擺滿了花，而且軟軟也乖乖坐著很可愛，看起來明天是該給清潔人員小費了。

晚上吃完晚餐後準備又要上車去 open ceremony。這個晚餐 buffet 五天都差不多是一樣的，也就是說 welcome dinner 不是什麼特別的 welcome；有室內跟室外兩邊，菜差不多，但今天日落後蚊子多得瘋狂，很多人都躲到室內吃晚餐。吃完走到大廳蚊子仍然非常多，拿出防蚊噴霧用了一下。搭車抵達的地點是 luxor 神廟，還沒下車就聽到旁邊的清真寺用很大的聲音廣播一個像是在大叫的東西，應該是某種宗教儀式？然後安檢的隊伍又排了好長。一出安檢就可以看到為了 open ceremony 而鋪設的場地，大致上應該是由木板為底上面鋪了一層黑色的布，還有一堆舞台跟螢幕。稍微逛了一下 luxor 神廟，但走回去到一半的時候大部分的照明就陸續被關掉，彷彿是在催促我們趕快回到座位，選手們就像有趨光性一樣慢慢往會場移動。
開場照慣例是個表演，很搶眼的是後面直接在神廟上雷射投影了 ICPC 2023 的字樣，字一直在閃爍而且還一直偷偷調整角度跟位置XD。
在這個就在神廟旁邊的會場周圍用探照燈到處照來照去的，頭頂上還有無人機在拍攝我們，感受到某種科技跟古文物的衝突感。
幾個人出來講講話之後，比較有趣的就是介紹所有有參加的大學，分不同區介紹，按照順序會先講只有參加 46 屆的大學、只有參加 47 屆的大學，以及兩屆都有隊伍參加的大學；昨天 team registration 的時候拍的照片這時候會被放出來。

結束之後似乎 ucup 有一群人聚集拍照，我們沒有拍到就先回飯店了。我們很晚才到飯店加上我在床上打混了蠻久，拖到洗完澡都快一點了，吹完頭髮出來才想到，糟糕會不會吵到他們。

會場與 challenge

Day 2

早上大方的 ot 放了五美金當小費。今天是第二天在這邊吃早餐，昨天的早餐我只有拿一個 omelet 而已，今天是拿了大概三盤 omelet，瘋狂排隊拿蛋。

早上先是在 Nile Hall 的 JetBrains 的 blind coding challenge，這裡是少數 46 屆跟 47 屆分開來的行程。JetBrains 先工商了一下他們自己之後，就是期待的 blind coding challenge 了。台上兩個人面對面坐，距離一個稍微長的桌子，一個負責看螢幕跟動滑鼠，另一個人操控鍵盤。目標就是解一個放在 codeforces 上的 mashup contest 盡量解越多題。選用的語言是 kotlin，似乎是用 JetBrains 他們的編輯器；解了一題之後似乎兩人會交換，A 跟 B 過的時候大家是用力歡呼加拍手，但沒能在時間內解出 C，大家看著兩個人在台上坐牢，身歷其境 XD。結束之後換 47 屆的，他們的兩人組是 tourist 跟 ecnerwala，聽說他們破台了，真羨慕。

下午是 huawei challenge，所有選手第一次聚集到正式賽的會場。雖然之前在 codeforces 上就有聽說會在「tent」比賽，但實際到了帳篷還是驚呆了。帳篷的位置就在我們的飯店附近（也就是說是島上），住其他飯店的人需要搭車過來。因為是正中午所以不是普通的熱，帳篷內側的周圍開了非常強的冷氣讓坐在中間的人感受到的溫度差不多是正常的，不過走去廁所的路上稍微靠近一點冷氣就覺得超級冷，一打開門又得頂著超級大太陽排流動廁所的隊伍，陽光刺眼到我很難睜開眼睛。
lunch box 和昨天的內容差不多，不過是直接放在我們的位子上，想到明天和後天也要吃這個鬼東西就覺得不能指望他們了。另外桌子上有瓶裝水跟很多筆記本和筆，筆記本裡面有各種方格，有 xy 軸的有密集一點的甚至有蜂窩六角形的。滑鼠墊上面跟我們的帽子一樣，都還是寫著前一個預定舉辦的地點 SSH 的字樣。
challenge 有點像是 AHC 的形式，就是針對一個（應該是）NPC 的問題用一些 heuristic 的方法想辦法弄出高分數。
稍微照著周柏宇說的方法寫了一份隨機之後傳上去只有 1300 分。後來改寫了模擬退火，ot 又寫了另外一個作法，但我們都無法突破 1600 分，記分板上大概有一百隊是 2900 以上 XD。我實在也很想睡覺，在桌子上小趴了一下。保持著一百以後的名次到比賽結束，還被傅老師過來關心。看了 tatyam 的推特才知道據說優勝會有兩百萬（日圓），而且感覺他們是有備而來，還用了什麼平行執行跟寫了 script 讓 output only 的部份能夠拿到盡量多的分數。

雖然說 challenge 的時候我們很累而且其實也不是我們擅長的，但一百多名還是讓我非常焦慮，所以我們提議回去之後不吃晚餐抓緊時間練一場，五日不團練面目可憎。抓了 8BQube 一起來練，我們就各自吃了一點泡麵（我幹了周柏宇十幾包泡麵中的一包來吃）後在各自飯店房間開打。BTW 飯店的網路很爛，不過漫遊是勉強可以打比賽的。
結果這場好難，而且打到最後真的幾乎是要睡著，開場十三題最終我們五小時做了六題，差一點可以做出第七題陰間 parser 題，而且我們除了簽到題以外每題都有罰時，總計 14 個 penalty，8BQube 他們也是慘烈，我們兩隊都吐槽今天 WA 成這樣該是把正賽的 quota 用完了吧。打一場暖暖手的效果應該已經達到，從六點打到十一點真的累，洗澡明天再說，很快的我就抱著軟軟入眠。

彩排/測機

Day 3

今天早餐一樣吃了很多蛋。ot 跟 tourist 一樣夾了一堆 sausage 來吃，他表示那是唯一可以吃的食物，得證 ot = tourist。
回去房間後洗澡，還有一點小睡的時間。

集合的地點是 Nile Hall。
因為是 dress rehearsal 所以跟正式賽的規格一樣，要求我們不能帶任何電子用品包含手機進場，所以我原本以為可以看著手機上的清單一個一個測機但其實不行。其他配件例如外套或是手錶也幾乎被禁止。台上螢幕寫著的 TODO list 有一項是 mohammed fouad 讓人非常在意，然後馬上就知道這是什麼了，一個大鬍子拿著麥克風好像在炒熱氣氛，但我唯一的印象就是他一直大聲喊 are you ready，總之應該就是本次大會的小丑人物。坐牢了一個小時後終於我們可以離開 Nile Hall 走路前往帳篷。我們進帳篷的時候需要拿一個像是入場證明的小單子，兩個主持人（其中一個是大鬍子）會輪流念進場的學校的名字。廁所和昨天只有一間不一樣，今天開始 46 屆和 47 屆必須用不同的廁所。但是入場之後我們去廁所被攔住，甚至被禁止離開我們這一排，想去廁所得先坐牢三十分鐘等開賽，而且我明明看到有人就直接走出去，坐牢感特別重。

意外的是題號從字母 O 開始編，和之前得知的一樣共有三份題本。測機的題目都是以前的 World Finals 題目，雖然有些不是我做的所以我沒有印象。每一題都還複製了一遍方便我們有更多題可以測（也就是說十二題的前六題和後六題是一樣的）。
team registration 的東西就放在桌上，包含 team reference document（也就是 codebook），於是 ot 就認真練習設定了一次環境。
__int128 跟 pbds 都可以用；沒有 MLE 的結果只有 RE 的結果；C++ 是嶄新的 C++ 20 非常棒。
我們也稍微做了一下幾題之後就開始測時間，基本上評測主機和我們的電腦跑的時間非常一致，簡單的操作跑個一秒 1e9 勉強是沒問題，加了 pragma 的 bitset 也是一樣可以跑到誇張快。無聊到繼續開題目，想說把 virtual 時賽中沒有 AC 的題目重新寫一次，結果這次也沒有在時間內推出可以過範測的東西。鍵盤打起來的感覺是有時候 shift 卡卡的不過基本上跟我們之前買來的那把一樣。

測了什麼

這裡有些是在前一天 challenge 做的，時間序有點忘記了。

• 編譯非常慢。從 htop 看來說，主要應該是因為我們的電腦有在跑錄影程式，所以很多效能被佔用。不過可以 precompile，而且不需要 root，方法是改成 #include "bits/stdc++.h" 然後在目前的資料夾建一個 ./bits/stdc++.h 裡面是 #include <bits/stdc++.h>，precompile 之後編譯的速度變快超多，而且傳上去也會動，好棒。
• 跟越南站的時候一樣，gnome-terminal 先按 F8 再按 F10 的時候會出現奇怪的 escape sequence，經過一些嘗試之後我們決定當天改用 konsole。
• 一抬頭就看得到記分板跟每題統計的跑馬燈，所以其實平常開另外一台電腦看榜不太犯罪（伏筆：正賽當天每題人數統計的跑馬燈似乎有壞掉）
• 決定比賽當天實施一寫完就印原則，彩排這天等了半小時印的 code 才來，有點害怕當天。列印要用 command line 指令。聽說有人把記分板列印出來用了很多紙，超好笑。另外聽說列印 0 byte 的東西例如 /dev/null 不會有紙出來。
• command line 有 submit 的指令跟各種語言編譯的指令，但應該沒有打算用。
• 命名成 t.cpp 在選檔案的時候就會自動幫你選題目是 T，到埃及前就已經知道的標準 domjudge feature，只是再確認一次。我們原本是把模板都打在 z.cpp，但因為這次題號會用到 z 所以 ot 表示如果隔天也是倒過來編號的話要改把我們開場的模板打在 a.cpp。
• 本機有 cpprefence 可以參考，不過不知道怎麼搜尋。結果正賽其實也沒用到。
• 不知道

測機結束後螢幕被強制關閉，我們原本以為必須待在原地，但看周圍其實有不少隊伍拿到手機了。原來似乎一般來說是要請 coach 拿行李，然後一結束馬上就能去旁觀席找他們拿，但今天我們的 coach no show，聽說 8BQube 他們直接原地坐牢兩小時，不過我的手機是就跟著 ot 的背包寄放在 Nile Hall，結束後憑著行李牌就能領。回到帳篷是 challenge 的頒獎典禮，不知道為什麼要遮住前三名後天才頒。然後是一個有關深度學習跟 GPU 硬體紅利的演講。

演講結束之後意外的還有一個 coach award，PJ 拿到兩個獎牌，但我們 coach 都 no show，所以不知道為什麼就變成有點尷尬是奇怪的四人組合上去領獎。
最後 coach award 也頒完了，竟然他把我們的螢幕重新打開，並且 domjudge 上還可以繼續傳，這表示其實看手機測機的行動可以現在執行 www（再不看行程表啊），稍微測了一下之後變成 ot 想偷打 kernel 的環節(X
聊了一下天之後就悠閒回飯店吃晚餐，畢竟要是今天再跟昨天一樣練應該反而會累死自己所以就不練了，還好昨天有把握時間暖一手。sean liu 是住另一個飯店的不過他今天跑來跟我們偷偷吃 jolie ville 的晚餐順便聊聊，不得不說他來 Luxor 的路上真的是多災多難。今天晚餐拿了兩罐放在冰桶裡面的汽水，飯店餐廳有很多寫著 ICPC only 的冰桶或是咖啡機之類的，sean liu 也拿了兩罐xd。晚餐用完後稍微又到處逛了一下，我是大概洗完澡十點半就睡了。

正賽

Day 4

今天就是正賽了，努力早睡睡到自然醒並且早餐吃飽一點，廁所在去集合之前上完。

賽前讓大家入場以及主持人喊話的環節實在令人煩躁，我甚至懷疑他們是想要用坐牢感來蓋過我們的緊張感。

就跟 dress rehearsal 的時候一樣，一打開題本果然是從 P 開始，非常不習慣。
跟平常的練習一樣由 ot 打 vimrc 跟處理環境，我從前面讀前半的題目，周柏宇從後面讀。

P 題第一眼感覺就在哪裡看過，但我決定先不仔細想丟給周柏宇就先繼續看下去。看完前五題感覺都不知道怎麼做。
Y 和 W 從記分板看起來大概是前兩題，於是 ot 寫 Y 後我照著周柏宇講的構造寫 W。因為怕 casework 自己寫爆而且搞不好之後還要改，所以果斷選擇先抄高斯消去法，結果範測的互動就 WA 了。這時他們兩人在旁邊討論 P 準備要上來寫，我就跳下去看自己哪裡寫錯，結果好像那組向量構造就是錯的，但我實在想不通一組好的向量條件是什麼，我們缺了什麼條件。W 實在是過太多隊了，只好瞎猜是隨機生一組就會過。
因為 P 在寫了所以 W 放置著跑去想金字塔 T 題，第一眼的想法就是選一個面壓平變成像是展開圖，然後再建邊跑最短路。
寫 P 的時候感覺很卡，ot 一直叫我不要看他寫xd，然後說他範測沒過跳下來修，結果其實半小時前就過範測了。
等 P 寫完我就跳上去寫 W 然後就 AC 了，P 等他說要丟上去也 AC 了。不知不覺已經過了一個小時，但目前三題待寫一題應該還在軌道上。
跟周柏宇確認後他也覺得 T 可以這樣寫，於是 ot 幫我抄完線段相交的模板後我就回去寫 T。在我寫的同時 U 的構造似乎也在順利進行。
我寫一寫之後範測就 WA 了，然後就發現我漏條件，壓平後不能從三角形的頂端直接往外走，修完之後仍然有不好的預感，但還是先趕快傳一遍讓 ot 可以開始寫下一題，submit 之後吃了個 RE。
我的猜測是我有一個地方 assert false，而這會在壓平後有兩個頂點重合的情況才會發生，我才想到原來兩個三角形會相交甚至重合。
修了幾次之後都還是過不了（4 tries），U 題也是修了很久之後仍然 WA，我們也只能當作沒看到名次慢慢掉到五十幾七十幾名繼續 debug。

途中 V 題周柏宇講了一個作法（難以聽懂的溝通障礙正常發揮），終於聽懂之後上去寫結果範測就沒過，de 了一個 bug 是我凸包的模板抄錯把一個 0 抄成 9，如果抄完就驗 hash 就馬上會發現了QQ 不過之後範測還是沒過，把凸包的內容印出來之後跳下來給周柏宇研究。
ot 表示他剛剛 U debug 到吐了去看了一下 T 題不是就三分搜套三分搜嗎？根本是天才，要不是有 ot 我就會一生卡在 T 了 QQ
我聽他的解釋覺得非常有道理於是他就上去寫，但一分鐘後我看到 struct Pyramid { int x1, x2, y1, y2 } 趕緊的跳上去自己把 T 開了。這題範測頗爛所以有測一些剛剛自己腦中亂生的測資（一小一大的貼在一起的金字塔，大的很高），才得知前面幾個版本的 T 在那個測資輸出的答案都是錯的，只是自己不會算術一味相信之前那個解是對的。這個寫法傳上去之後順利一發就過了，看過題人數就應該要是這個寫法才對。U 陸續挑出一堆 bug，但還沒過；周柏宇表示 V 是我需要先把兩個骰子的順序按照會不會贏交換，交換之後我就輸出跟範測一樣的答案了。把對稱的 case 寫好後也就上傳，吃了個 WA，然後就發現我在算要不要交換的地方有溢位，再傳就過了，雖然浪費了一次罰時但可以說感覺清爽多了。十分鐘之後 U 也 AC 了，after 5 tries。至此比賽已經過三小時。

現在我們六題+超級爆炸罰時，大概二十三十名，但 Q 題是一個超級多人做出來的題目，所以推測我們也可以開出來。記分板上現在 R, X 都是 MIT 獨開的題目，也就是說七題就會跟第二名同題數了；另外前段隊伍都在嘗試 R，看起來應該是 Q 之後的下一題。
但周柏宇表示他範測算不出正確的答案要我先做一下，他去做 R，結果我搞了半天也算不出對得上範測的答案（我在這邊浪費時間做小學生算術好像很虧）。Q 是一個算期望值的題目，想法大致上是期望值可以相加，並且拆成每一步的期望值後應該要很好算。R 目前的進度姑且可以說是每個 BCC 要分開做，電腦為了不空機先抄了 BCC 的模板，之後又稍微針對一個 BCC 恰好兩個環的情形打表了一下，發現可以弄出來的 permutation 數量不是 n! 就是 n!/2。
因為 Q 實在太多人過了，我提議我用電腦暴力跑一下範測確認我們理解沒有錯誤，然後順便再把我們分類的每一步的期望值打出來，看看自己是哪裡算錯了，把跑出來的結果看了一遍之後發現被自己笨死，有一個 case 根本就不該算。終於寫了個 $n^2$ 過了範測，趕緊改成 BIT 過了這題，這種 div1 A/B 的題目我們兩個人範測都算錯拖到三小時四十分才過實在是有點慘。

過了當下的名次仍然只有 14 名，此時我們要拿牌一定要做出第八題，但其實做了八題也不一定能拿牌，有大概四五隊已經八題，且都是開 R，只有 mit 開了 X。
剩下只有四題 RSXZ，X 當時周柏宇宣稱是大模擬；Z 只有 mit 瘋狂傳了一波之後就停了，猜測我們不該碰 Z；S 則是在第一個小時周柏宇就跳出來請 ot 寫了一個範測就會 WA 的假解，我不敢再碰。
時間只剩下一小時二十分鐘，我們只能相信全力做出 R 有機會拿牌，之後的事情之後再說。

周柏宇讓 ot 跳上去開始寫暴力打表所有邊雙連通圖的答案（但我總有一種記憶是某題也在打表所有簡單環然後寫到爆炸），體感時間過了很久。
根據之前的打表可以知道 permutation 數量是 n!/2 的那些都是兩個奇環相黏，而其實湊不出來的那一半排列就是奇偶性不對的排列，因為奇環 rotate 一次是偶置換（？）
我在下面的時候周柏宇表示就先貸款說「要判奇偶性的特殊情況只有只有點仙人掌每個環都是奇環的時候才要判」的話，我們能不能寫出一個作法，然後我就想了一個如何判一個圖是每個環都是奇環的點仙人掌。還有周柏宇不知道為什麼像是有個錯覺是覺得有重複的東西就變很難，明明最近感覺就有遇到一個類似的東西（如果有重複的東西的話，既可以是奇置換也可以是偶置換，否則置換的奇偶性就被確定了）。稍微想了五分鐘怎麼實做，現在就是到底這個猜測對不對的問題。ot 似乎寫出了 bug 要跳下來，我就先上去寫了一點東西，再被搖下來之後那份暴力打表還是有 bug，所以就決定乾脆賭下去我先一路寫完傳上去。
因為有先想過怎麼實做所以我體感是寫得很順，範測和一些他們構的比較強一點的測資通過之後就丟上去…然後吃個 WA，血都吐乾了，要是那個猜測是錯的怎麼辦？我們有什麼備案？ot 先繼續修暴力對拍，我們就印 code 出來看，發現我有一個地方忘記把一個 flag 設成 true，真沒有愧對這個變數的爛命名，改掉之後傳上去三個人就瘋狂盯著看有沒有過。過了之後的高興並沒有持續太久，因為我們剩下半小時沒有題目可以做了。
因為 X 被說是大模擬，所以我聽完 X 之後又跑去看了一下 Z，這時候大概已經沒什麼腦細胞了，明明榜就是指引我們做 X 但我一直沒有放在心中想。最後 ot 跳上去假裝寫了一下 X 的讀入部份之後，就只剩下一兩分鐘給我們傳 strategic submission 了。

賽後與心得

賽後我們迅速的從傅老師那邊拿到手機，但比較重要的是到底有幾個人八題了。
ot 和周柏宇發揮社牛力到處去問，然後 chenjb 甚至也跑來問我們有沒有八題。
最後還是有一兩隊沒有問到，心上仍然綁著大石頭。

因為接下來就要去 secret place 開板+閉幕儀式了（這時候滑推特才學到日本那邊把滾榜/開板是叫 Yes/No(?)），所以大家被趕上遊覽車，我們匆忙的把氣球底座和一些東西放到飯店再跑上車。
車程非常意外的久，大概四十分鐘，在車上小睡了二十分鐘。
下車後同樣是慣例的安檢，往前走幾步感覺到這裡是異常的空曠，才聽說我們到的地方就是帝王谷的哈斯普蘇女王大殿。
空氣中微微的瀰漫著沙，跟著人群往前走卻是在一片沙漠中搭出來的最終舞台，往前看的參考物幾乎只有 ICPC 的 logo 投影，靠近點看還會發現仍然是直接投影在大殿上。我們台大七個人找了一桌坐下來，接著就是一些舞蹈表演還有冗長的演講以及廣告影片，不過我們則是專心的在大會架設好的餐桌上用餐。可以說烤肉和飯的部份不錯，但其他糊糊或是非常生又硬的蔬果實在有點難吃下去。
這邊順便頒了前幾天偷偷遮住的 challenge 前三名，恭喜東工大優勝（據說有 USD 13000 獎金）。
一個小插曲是不知道為什麼有一群 staff 像是喝了酒超級 high，把人抬起來歡呼，而且他們離舞台有點距離感覺沒人制止他們，最後也不知道怎麼就停下來了。

總之最後來到了開板環節，主持人穆罕默德有點吵，而且大會決定 46 屆和 47 屆的板交替開，輪流把低題數的開一部分之後念獎項再換另一邊，中途還會有各種獎項例如首殺或是 regional champion 要頒，等得心急如焚。
U of wroclaw，ITMO 都沒有開出第八題，stanford 也是兩題 pending 都沒開出來，最後我們沉一沉沒有沉到銅牌線下，剛好維持在第十二名，也是解出八題的隊伍中罰時最高的。可以說幸運拿到了銅牌。
接著就是拍照環節，我的軟軟被強制不能上台qq。
上台的時候一直不知道該或不該握手或鞠躬，該面對哪裡手要怎麼擺，總之是過去了。現在回去看直播看得我尬癌發作。
銅牌的四隊有一起合照，意外的得到跟傳說中的 yutaka 的一張合照（？）雖然是很多人的。

comment about 本次表現

如果我們想要得更好的牌的話，首先最重要的是不要在 T 和 U 卡題導致第二小時黑洞，接著應該就是 Q 範測算錯拖超級晚才 AC，然後就是必須賭 R 賭的更用力，直接相信他遲早會過而另外兩個隊友在底下做 X 題。如果沒做出 X 的話罰時必須要超級好才能銀牌，但如果以上幾個問題都改善的話，我們應該會有一小時多可以做 X 題，稍微偷看了一下解，我認為三個人討論是有機會做出 X 的（當然也可能我們風向歪向 S，而且我們當天結束到回飯店其實也沒有討論出 X 該怎麼做）。
另外，World Finals 正式賽真的大家都會軟手，看到牌線下有好幾隊原本認為會得牌的隊伍，可以說，World Finals 就是在比誰不軟手、誰能在不舒服又奇怪的環境發揮。我自己感覺也有一些平常該做的事不知道為什麼就忘記了，例如我今天只有去一次廁所，而且整個 lunch box 都沒打開來吃（其實可以吃一下甜點醒腦的）。

本次實際上有用到的模板除了 debug macro 以外，有凸包、KMP、BCC（找橋）、高斯消去，對面 47 屆的題目似乎頂多也就多考察個質因數分解，最多最多若把凸包那題做難了可能會用到全整的半平面交（如果不是全整的話要調對 EPS）；至於線段相交反而是沒有對最終的 AC 解有貢獻，有點 codebook 不如放個三分搜的感覺。我想說的是，在 codebook 準備一些毒瘤東西其實對 WF 幫助不太大，會出這些毒瘤東西的可能只會是 regional 比賽，反倒是把基本的模板整備好很重要，尤其是我認為模板的 md5 hash 應該積極引入，回去看直播會看到有些隊伍像是怕模板抄錯在花時間對，而我們則是把模板的內容整理成好用的樣子，要用的時候就百分之百照抄，如果抄錯立刻就能被 hash 抓出來，很有幫助。

郊遊

Day 5

隔天原本 sean liu 有問我們要不要去一個 excursion，但那個行程要早上八點集合，我們最後因為實在太累也不敢跟這個行程了。傅老師說中午十一點半集合，我們差不多睡自然醒睡到八點半之後吃個早餐再混一下，洗個澡就差不多了。老師中午集合後表示我們中餐跟晚餐就吃 KFC 跟麥當勞，決定先去 KFC，搭計程車雖然遇到一點小風波不過 KFC 是很快的順利就到了。門口旁的髒亂程度讓人不敢恭維，但入店吹冷氣實在很爽。菜單有寫英文，而且店員懂英文，價格體感和台灣差不多，不過不收美金現金只好請 BB 刷卡。漢堡炸雞跟薯條都中規中矩，小瓶裝的百事可樂也沒有減低我們吃了數天飯店 buffet、lunch box 後吃到速食的感動。

吃完之後老師表示我們先回飯店的話太虧，就在附近繞繞慢慢走去麥當勞，但一走出冷氣房真的很讓人後悔沒有多帶一瓶水出門，感覺隨時都會中暑或是脫水。越走越覺得我的穿著跟儲水量都沒有準備好在這種太陽下待一個下午。原本打算去木乃伊博物館，結果走到一半發現他是下午五點才開，原來凡是一個正常人都不會在正中午出來活動。最後我們總算轉向麥當勞先每個人買了一杯 large 的飲料止渴。店裡看到一個在剪片的人，而且他上的字幕竟然是日文很有趣。在冷氣房待好待足之後我們才又走出去慢慢走到木乃伊博物館參觀。門口一樣有安檢。參觀結束後大約也日落了，我們回到麥當勞買晚餐，但是幾乎都坐滿人了，於是我們都覺得應該要外帶回飯店吃了。跟 KFC 比起來麥當勞的內容和台灣更加一致，我因為蠻餓的所以點了好多好多，所以甚至比我在台灣會點的還貴一點，回去之後才想起來還有前一天的 lunch box 沒吃，最終 lunch box 還是浪費了 2.5 人份。

今天一整天走在路上常常會有人喊說 taxi taxi，或是問你搭船或馬車，或是推銷你隨機紀念品的，有的人還會用中文說你好。他們幾乎都會強調只要一美元、很便宜，我猜是真的很便宜，但我也沒有想去搭船、買紀念品的理由。

吃完晚餐之後努力早睡，因為我們一群人報名了熱氣球明天四點必須在大廳集合。

Day 6

睡眼惺忪的起來到飯店大廳集合，等接駁車載我們到熱氣球的地點。
據說是因為天氣的關係遲遲無法升空，我們也就待在大廳乾等，等到都已經日出了我們才搭車出發。
清大也參加了這個行程，雖然在不同飯店但是是一起乾等了兩個小時，結果這個車程竟然需要從島上先開到東岸再開到西岸（幾乎是閉幕典禮那邊），我也只好在車上小睡了一下。

到了目的地之後可以說是沙塵滾滾，幸好有獎勵元發給大家口罩才不會太不舒服。熱氣球的組裝跟加熱比想像中的大聲很多，我們靠近一點之後幾乎都要大吼才能聽到對方講話。升空之後很怕手機掉下去但還是努力拍了一些照片，而且從空中可以俯瞰閉幕典禮的那個大殿，大殿前的舞台已經幾乎拆除完了。在空中的時候機長（？）一開火加熱空氣就會大聲到沒人可以講話。裝著我們的籃子在慢慢旋轉，並且風有慢慢的把我們往東邊吹，稍微可以近一點的看到尼羅河。最終我們正常降落在一塊田旁邊，是很特別的經驗。

結束了？

回到飯店後，因為是下午兩點半的飛機所以我們打算搭乘十二點官方的 shuttle bus，但好像其實這一天就已經不會有 shuttle bus 了，大部分隊伍例如交大、東大都是在前一天就搭飛機走了。ICPC 給的紀念品真的好多，花了一點時間盡量塞進行李裡，並把行李整理好。

還沒搭上車埃及航空就宣告他們會延遲一小時，我們意識到不會有 shuttle bus 之後才趕快搖了計程車前往機場，叫來的計程車實在很狂野，把行李用綁的綁在車頂上的置物空間，速度計沒有在工作而且他又開超級快，每次轉彎我都怕七個人的行李會不會全掉下去。
這裡比去程的時候混亂多了，還沒進航廈不知道為什麼就要我們出示護照，然後那個要我們出示護照的工作人員還問我們是不是 China，旁邊就有兩個女的就說 one china one china，莫名其妙。一進去又是安檢。然後 olmrgcsi 的護照因為神秘原因從門口走過安檢再走到 checkin 櫃台的二十公尺內消失了兩次，嚇死人。機場共有兩個人幫我們推行李之後要了小費，其中過了安檢幫我們推五公尺到 checkin 櫃台的那個超級無恥要了三美金 wtf，真的是回程比去程可怕多了。
到登機口後 BB 發現明明是登機時間了飛機好像還卡在開羅，我們等了好久好久還拿了每人一瓶似乎是補償的飲料，最後我們可以上飛機的時候已經延誤了一百分鐘了，我們心想這下在開羅得要動作快點。
機上餐點跟來的時候一樣是一個簡單的小蛋糕，我基本上在機上是睡覺。這次起飛降落倒是比去程平穩。

下飛機之後我們等了好久行李才跑出來，然後我們又需要跑到另一個航廈再過安檢（超 tm 久= =）才能去 checkin 櫃台，拖一拖到起飛前 53 分鐘才到 checkin 櫃台，排在我們前面的人行李似乎上去了，但我們和後面幾個人被拒絕了，emirates 表示這個延誤不干他們的事，他們飛機是準時起飛的，但很明顯這也不是我們的責任而是因為 EGA 延誤了，然後櫃台人員就一臉郭的下班走掉了，留我們一群轉 emirates 的不知道該怎麼辦。

慌亂

現在麻煩的是因為我們是一大群人，而且 emirates 看起來不知道是要放生我們還是我們有辦法 rebook，也不知道買了機票的話誰能負責，台灣現在的時間是大半夜，旅行社或是系辦或是 BB 公司的人都很難聯絡上。所以可靠的大人 ot 和 BB 就去到處探索，我們剩下的五六個人就或坐或站在 checkin 櫃台前面待著。我們現在在過了安檢的關內，他們說如果沒有 good reason 的話很難離開這個關出去（明明就不是 passport control 也不是 custom???），並且這裡也沒有 emirates 的客服櫃台，我們要處理的話只能打電話去，但偏偏剛好前兩天杜拜淹大水的事件讓客服很難打進去。
經過一番折騰，問了各種信用卡跟保險公司，還跑去問海豹（？）最後接通了一次 emirates 電話，由 BB 跟他們溝通，但因為我們的票變成很詭異的樣子所以那位客服又轉接給他的同事處理，然後就斷掉了。我們等到下一班的 checkin 人員來跟他們試著溝通，但他們似乎也不想或者其實也無法處理。於是我們折騰了四個小時在 emirates 上最終還是得認賠殺出，開始尋找購買其他航班的選項。原本要買卡達航空了但他們限制是必須要在四小時還三小時前買機票，踩到一個從來不知道的限制。最終幸好買到了另一家阿曼航空凌晨兩點飛往曼谷的機票，先趕快逃走開羅機場這個鬼地方再想辦法從曼谷回台北。當初肯定是想都沒想過會搭這種新奇的航空又去（我沒去過的）曼谷機場。
順帶一提，跟我們同一班的另外幾位同樣是轉 emirates 的 ICPC 選手一位是從埃及航空那邊拿到一張往杜拜的票，另一團是直接認賠跑去搭卡達航空了，也不知道是該怪 emirates 還是怪 EGA。

逃走

Day 7 (unexpected)

凌晨兩點趕上機，大部分都是讀阿拉伯文的中東乘客，此外很討厭的是我右邊坐了一個起飛還在一直講電話又一直擠過來的胖子。
這架飛機只有一個走到，右邊那個胖子又吃完後很快就睡著，導致我整體感受是非常擠的。甚至上方行李櫃沒有地方可以放我的背包只能放前方座位底下，腳快縮到斷掉。坐定位才發現自己好渴，但我又非常累，邊懷疑自己會渴死一邊沉睡，聞到飛機餐出來的香味時彷彿是救世主降臨，畢竟我們除了小蛋糕以外是沒有吃午餐，趕緊的扒完後好好珍惜他順便給的那瓶水，省著慢慢喝。稍微玩了一點機上的遊戲結果玩到睡著，實在是很睏，畢竟前一天還早起去熱氣球。中間的座位真的很不舒服很難睡，保持著很睏的狀態到了阿曼。終於不用再像埃及那樣有事沒事就瘋狂安檢了，這裡的流程快也人性化很多，轉機還有麥當勞可以吃，不過我們這群人好像只有買了一小瓶飲料就要價台幣一百三十。很重要的是這邊有飲水機跟乾淨的廁所，可以說至少我們看得到的地方很人性化。

等待了不久我們坐上了往曼谷的飛機，這架阿曼-曼谷的飛機看起來比開羅-阿曼的飛機好多了，首先他有兩個走道看起來就比較厲害xd。飛機餐跟前一班飛機一樣是 chicken rice：用很長很中東的米包住一些雞肉作為主食，不過這班班機的主食醬汁和甜點都讓我感覺比較好吃，沒有理由。依然是中間的座位依然很難睡。抵達曼谷之後在機場逛了一下，這邊好多日式料理是想被吐槽嗎xd 我們吃了久違的東亞食物泰式料理，喝到泰奶有種莫名感動。這也是意外的第一次入境泰國，不過我們沒有離開機場，只在機場吃晚餐，等待最後回家的華航班機。

華航上面的飛機餐我選了雞肉義大利麵，入口時有種終於吃到像在家會吃到的食物的感覺，果然飛機餐還是習慣台灣的不習慣中東航空的。明明是台灣的航空但機上娛樂的麻將卻是日麻（richi mahjong），所以我跟波路都打開來玩了一下，但好像不知道怎麼結束，打到西場都還繼續打，似乎要打飛才能結束，而且也沒有流局罰符，感覺細節規則蠻微妙的，最終我吃完飛機餐後是玩到睡著了，在打瞌睡下回到台灣。不得不吐槽這趟不知道是亂流很強還是怎樣，起飛降落的搖晃跟去程埃及航空有得比。

回到家已經是十點的事情，全身髒兮兮巴不得趕緊去洗澡完睡覺，這才是真的感受到風塵僕僕吧？

random tips

旅程總算劃下句點，這邊稍微紀錄一下我這次感覺沒有準備好的旅行細節。

• 帶著機票的文件出門
• 帶美金的話帶多點小張的美金，比較實用
• 帶張信用卡方便在海外刷
• 帶點簡單的零食在需要的時候可以吃
• 帶 USB-A 的線而不是 USB Type-C 的線；像我們這次搭的阿聯酋雖然有萬用插座，但其他航空都只有一個 USB-A 的充電孔（埃及航空除外，什麼都沒有）

結

wf 真的挺折騰的，假如說回程遇到的這些問題我們是去程遇到的話，感覺狀態會大大受影響。之前耳聞的台大名次是第三第四第五，這次感覺拼死拼活才勉強保住獎牌，不知道是台大不進取還是其他國太卷？又或者我們需要幸運一點遇到適合我們的題目？但還有牌應該可以知足了，這次連日本的所有隊伍都是銅牌，實在是競爭激烈。

把整個 wf 紀錄下來實在花好多時間！
下一篇文章如果有空的話希望會是先寫上學期的修課心得。