APIO 2023
今年 TOI 決定要開始把 APIO 算進二階成績裡面，雖然說根據邪惡表格我似乎不會被逆，
但是在選訓的時候我有 virtual APIO 2019 然後打的很爛，高一的時候有 virtual 過 2021，同樣也打的很糟，
二階結束之後 virtual 了 APIO 2022 然後有拿到金牌，可是整個二階過後大概就只有練習這個，現在想起來有點太燒雞了。
測機
今年 APIO 是 5/20 到 5/21 （星期六日），台灣是選 5/20 打，然後上禮拜五的時候 TOI 宣稱他們有寄測試帳號給我們，
不過我們都沒收到，寄信給 TOI 之後他們回了帳號密碼跟 CMS 的 admin 介面，
等我決定去測機的時候，我一打開發現他給我的連結是 port 8889 的 admin 介面，所以我猜他們沒有改 ContestWebServer 的 port，改成 8888 就進去了，
測機有三題，第一題是水題，第二題是動態加點或刪點問有沒有一個點不在當下的點集但以他為根的時候至少三個子樹都有點，第三題是詭譎互動題，詳細我有點忘了，
第一題亂寫亂寫我得到 50 分（Subtask 3, 4），這時候題目的兩個參數 $Q$ 跟 $S$ 我看反了，
然後這樣導致我範測一理解錯，改了一個錯誤的理解拿到 80 分（Subtask 2, 3, 4），
搞很久才發現我看錯那兩個參數了，改過來才拿到滿分，不知道在幹嘛。
第二題我大概想到了可是我懶的寫，高嘉泓說他寫了一個很乾淨的作法，超強。
賽前
TOI 說前一天晚上八點前在捷絲旅報到，報到的時候要順便訂比賽當天下午的 pizza 所以卡了很久（？
報到完就沒什麼好說的了，晚上的時候我跟 Darren 在討論為什麼 2022 四模 A 我們的做法是不是可以拿不錯的分數，然後就快樂睡覺了。
早上起來我們在讀規則，TOI 說我們等等比賽的時候要自己帶測試的帳號密碼進去，因為跟正式的帳號密碼一樣，這樣要是有人事先分享或者不小心知道不是就會大作弊嗎，超級怪。
還有我以為比照模考的意思是 TOI 會用路由器鎖我們只能連到他們 CMS 的介面，可是實際上好像是可以連外網，所以我們在想要怎麼把我們的東西放到網路上，還好我從以前到現在幾乎所有 code 都在一個 repo 裡面，所以我只要 push 然後開成 public 就完事，打 OI 突然變成軍備競賽（X
比賽
這次的考場是 E202，到考場的時候我們發現今年 TOI 的筆電上有 VSCode 了，所以可以期待一下以後的模考可以用。
考場內 TOI 有印好中文跟英文的題本，開賽的時候登入然後 Start 要自己按開始，我以為都登記好參賽時間了 CMS 應該可以直接設定參賽時間，導致結束的時候大家會差個一兩分鐘之類的。
A 是一題水圖論題，看完題目的時候我就知道 $K$ 其實是 $\log C + \log N$ 量級的東西，而只有最後一個 3 分 subtask 是這個東西就讓我更清楚他是對的。
B 看起來是一道奇怪的資料結構題，想了一下沒有很多想法，
C 是一道 3-steps 的電路題，看懂題目花了我超級多時間，基本上就是用 16 種真值表的電路算詭譎的東西，
我先去發了一個 C 的問題然後動手寫 A，不過他似乎不能回答我 C 的問題，因為這個問題的答案其實題本裡面有，不過那個部分應該是小問題所以應該不會怎樣，A 寫完傳上去一直等 compile 我以為我 CE 了，等了一段時間發現他有 Announcement 說 judge 卡住了要等大概一段時間才會得到結果，所以我就先去思考 B 跟 C。
0:45 A 97
subtask 8 是 WA，所以應該就是 $K$ 太小了，把它改成最多 80 再傳一次，
這時候我的 B 沒有任何想法，可是 C 的 12 分超級好拿，然後 54 分很好賺，所以我就先去寫了一個加法器跟一個乘法器寫 C，
印象中這時候 Announcement 說 submission 要過半小時才會有結果。
1:01 A 100
大概 A 確定有 100 的時候我的 C 12 寫完傳上去了，
這時候想想發現 C 66 我只要把名子換成 bit，然後假設 Alice 拿著名子 $n_i$ 的人數字是 $a_i$，Bob 拿著 $s_i$ 寄給 $r_i$，那我只要算
$$\sum_{j = 0}^{m - 1}[n_j = r_i]\left(\sum_{i = 0}^{n - 1}[n_i = s_j]a_i\right)$$
就好，
這樣可以快樂 $nm$ 次比對跟加法就做完了，
1:34 C 12
傳上去之後去想 B，B 真的對後面的子題一點頭緒都沒有所以決定開始喇分數，我先是直接開抄我的 PBDS 然後快樂寫完 28 分，之後開始想 7、12 跟 13 分要怎麼做，
B 的 7 分是遞增再遞減，我一開始看成是兩段遞增，不過作法幾乎沒差，而且還簡單還多，思考一下推了東西也傳上去了。
2:16 C 12
出問題了，一測發現不得了，我的解在亂跑，
後來發現是我的字串沒有考慮到長度可能不足 4，所以改完之後再傳一次等大概 30 分鐘，
2:22 B 28
12 分是值域只有 1, 2, 3，有點難所以我就去外面想想，後來想到 2 不用處理，答案直接跟 2 的出現次數取 max 就好，所以我就寫了 BIT 算那種中位數的東西，
2:48 C 66
2:55 B 7
這時候 judge 說大概要等 45 分鐘，我 B 12 傳上去之後就開始想 B 13，想一想想到了一個 $\mathcal O(N \log N)$ 的線段樹作法，基本上就是看兩個出現的東西中間必須拿，前後要拿兩個前綴後綴調整讓這個東西在裡面，因為連續性我只需要考慮可以達到的區間就好了，可是線段樹有點肥然後它還要被修改查詢 $10^6$ 次，所以我有一點不敢寫，
3:11 B 0
Wrong Answer，直接開本機對拍發現我 3 的時候忘記把數字改掉了，先傳上去然後多拍幾次確定沒有大問題之後繼續往下想，
想一想我記得全國賽的快快 judge 可以跑得過這麼多次的詢問，然後 IOI 2018 Seats 的修改量似乎也有這麼大，我就直接開始寫下去了。
寫完大概比賽還有半小時，我先傳了一次之後本機對拍，一拍出問題了，發現我出現次數只有 1 的時候忘記改線段樹然後直接繼續做，修改完再傳上去然後測時間，但我還是沒有很放心所以傳了一個有 pragma 的版本。
這時候官方說 judge 要等一小時才有結果，真的是爛透了。 快結束的時候多跑出來了一筆結果，
3:53 B 12
然後比賽就結束了，TOI 有把題本收走，雖然我不太確定為什麼，賽後我們發現 judge 還是可以上去看題目跟 submission 所以一點意義都沒有吧。
下面是比賽完才出來的 submission：
4:36 B 0
4:39 B 13
4:42 B 13
賽後
賽後我們花了一點時間才知道系統還可以登入然後看結果，大概再等了一小時我的 13 分有跑出來拿到了，當下覺得蠻開心的，在這個爛 judge 上我還可以拿到至少不差的分數，
最後分數是
| task | sum | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| A cyberland | ||||||||||
| B sequence | 22 | 18 | 60 | |||||||
| C abc | 18 | 10 | 6 | 66 |
牌位截至目前還沒有出來（現在似乎是等待 appeal 環節），不過我猜我有很高的機率是銀牌。
明天還要考台大二階的筆試，所以我就繼續待在台北，
晚上有空的時候我想一想，想到說 B 用這個做法，當我遇到同樣的時候它可以是小於也可以是大於也可以是一樣，所以就能對某個 $k$ 做這樣的一件事然後用詢問二分搜答案是不是 $\geq k$，比賽中我有嘗試二分搜但是我一直卡在 $=k$ 有很多反例，這個做法要兩個 $\log$，但要是我把每一段都記錄下來，然後對每個數字分別二分搜，那其中一個 $\log$ 就消失了，而我這樣就會多 40 分，
越想心情開始有點糟，自己把一個滿分丟掉然後大概也沒有機會金牌了，
雖然說第一次打正式的 APIO 或許遇到這樣的爛 judge 可能算是表現的還可以了，但是這代表要是我最後去打 IOI 的話，我的實力還是不夠。
至少今年的題目讓我知道 APIO 可能越來越朝著正常的 OI 方向邁進了（？
雖然我未來大概也沒有機會參加 APIO 了吧。