APIO 2020
這是一篇拖了兩個月的心得 (X)，因為比賽時間正式結束前都要保密題目，而且後來又有 open contest，我就想說等 open contest 結束再寫心得，結果就拖到現在了，希望我沒有忘記太多。其實我本來想要把我的 code 放上來，但過太久比賽系統已經關了 QQ。
比賽那天是 8/15，這個暑假過得有夠忙，有 IONC、資訊營和暑培，而且資訊營隔天馬上就緊接著 APIO，一點喘息的時間都沒有，還好打得還不錯。
比賽前一週左右都是測機時間，但因為資訊營太忙，我到前一天才想起來，結果測機時間已經結束了，而且比賽系統不是 cms，所以我是在完全不知道系統長怎樣的情況去比，也不知道分數有沒有聯集，還好一切都跟我的想像差不多，分數有聯集，而且會把每一筆的結果顯示出來，不會只顯示到第一個錯的。
APIO 的時間是每個國家可以自己選五個小時打，臺灣就是 8/15 的下午一點到六點，所以快中午再到就好。中午午餐有一碗麵、一包薯條和一杯飲料，開始前就是一邊吃一邊耍廢。電腦是用二階時用的鍵位超怪筆電，作業系統有 Windows 和 Ubuntu 可以選，聽說建議用 Windows 打，因為 Ubuntu 沒測試過 (??)，但沒有 CLion 的時候我習慣用 Ubuntu 打比賽而且 Ubuntu 有內建踩地雷，所以還是用 Ubuntu 了。因為比賽允許查資料，我就在開賽前先把 codebook 抓下來，就不用手打 default code 了。
子題和限制可以去 OJ.UZ 看。
pA 63/100
有一道牆分成 格，從 到 編號，還有 種顏色，從 到 編號，第 格牆要被塗成顏色 。 有 個工人，從 到 編號，每個工人都有一些自己喜歡的顏色，且只願意塗自己喜歡的顏色。 每次操作可以選擇 和 ， 且 ，表示對於 ，要叫工人 去塗第 格牆。 第 格牆只要被塗顏色，顏色在任何時刻都必須是 ，所以工人 喜歡的顏色必須要有 。 求最少幾個操作可以完成目標。
第一個子題是每種顏色只被最多一個工人喜歡，所以對於每個 都可以知道要選哪個 ，DP 一下就能線性。
剩下到第四個子題可以 DP，算每對 可以塗多長，最後再 DP 一次。我寫的時候一直 WA，所以就拿小測資暴力對拍，發現是 DP 寫錯。小測資滿有用的，對於 debug 很有幫助。
pB 50/100
有一張無向簡單圖， 個點 條邊，都從 開始編號，邊有權重。 有 筆詢問，每筆詢問表示有兩台車分別在節點 和 ，這兩台車要分別要到節點 和 ，它們不能在同一時間在同個節點上，也不能同時經過某條邊（不一定所有時間都要移動），求兩台車經過的所有邊中，邊權最大的，最小可以是多少，可能無解。 強制在線。
子題一是圖成數個鏈或環，我本來以為只要除了兩個點之間的路徑以外，有別的點就好，然後就一直 WA，想了一下發現是兩個節點所在的連通塊不是鏈就有解，所以就先把每個連通塊處理好，環的話答案就是環上權重最大的那條邊。
子題二是星狀圖，一樣就是直接判圖是不是鏈就好了。子題三是 暴力，可以拿來對拍。
子題一很佛，給了超有用的提示，子題四要 才能過，有了只有鏈不行的結論，就只要把邊由小到大依序加到圖上，一邊維護連通塊是不是環就好了，可以用 DSU 維護。
然後我寫心得的時候忽然想到滿分解 OAO，先做一次剛剛的加邊，兩個 set union 的時候弄一個 dummy vertex 當它們兩個的根節點（如果已經在同一個 set，就加一個點當新的根），在這個節點記錄現在連通塊是不是鏈、最大權重是多少，最後會蓋出一棵有 個點的樹，詢問的時候，就找兩個點的共同祖先中，最低的連通塊不是鏈的，那個節點記錄的權重就是答案了。賽中怎麼沒想到 QQ。
pC 26/100
有一棵 個節點的樹，點和邊編號都從 開始，每條邊的長度都是 ，兩點的距離記作 ，求一個點的 permutation ，使得 。 沒有這麼簡單就結束，圖沒有給，但是可以詢問最多 次，每次詢問可以問兩點之間的距離為何，或是詢問兩點 、，有多少點 滿足 到 的路徑經過 。
前兩個子題都可以直接把整張圖問出來，然後先找樹直徑其中一端當第一個點，再不斷找和已經上一個放進答案的點距離最遠的點，放進答案裡。
子題三是 complete binary tree，而且編號是 heap index，寫到這的時候已經剩沒多少時間了，點的數量也沒辦法用剛剛的作法，所以我試圖亂猜出規律，結果丟上去 RE。
總分：139/300 排名：國際 88（銅牌），TWN 4
今年臺灣燒雞，拿了六銅，然後中國拿了 9 個金，強死。
第一次打五小時三題的比賽，其實氣氛滿輕鬆的，畢竟沒有悠關人生大事。
pB 有個小插曲，就是我平常都會用 GDB 抓 RE，不過做這題的時候一直 SIGTRAP，backtrace 也找不到是哪裡有問題，這問題通常會發生在陣列出界，所以我就開始找是哪裡有問題，結果發現是只要我去讀 grader 傳來的變數就會這樣，搞了很久以後決定試著不要 GDB，然後就可以正常執行了？！？！之後我就沒有用 GDB，不過就很怕 RE 會不知道怎麼抓，還好後來都沒有本機 RE 了。但是這件事花了我半個小時，有夠糟糕。
這次最大的敗筆還是 GDB 的問題弄太久 QQ，不過後來我在做 pC 的時候又開回來，然後又可以正常跑了，感覺是 pB grader 的問題。
這是高一的最後一場比賽了，算是為高一的競賽生活畫下一個不錯的句點，這一年過得很充實，也進步了很多，從本來的青人到現在的橘人、從去年全國賽燒雞成 27 名到今年上了二階，我都不知道我是怎麼做到的。其實我滿慶幸有上二階的，不然我都沒在做學習歷程，想回頭準備學測應該不太可能，也沒辦法那麼自在的打競程了。
最後，官網說會有實體的參賽證明和獎牌，但我現在只收到電子版的參賽證明 QQ，希望不要 IOI 2022 才發 (?)。