又到了 APIO 了，去年因為疫情有延後，像今年一樣辦在 5 月才是正常的。本來應該要到師大比，但是剛好這陣子疫情爆發變成線上線上賽 QQ。這篇文大部分是在比賽完當天就寫的，但等 Open Contest 結束才會發。
這次每一題的子題都切得超級細，每題都有 7~8 個子題，只是前面的子題的分數都少得可憐 QQ。子題和限制就自己看題本啦。
題目裡有中文
題目
pA Hexagonal Territory
3 / 6 / 11 / 12 / 15 / 19 / 18 / 16 = 20
有一個無限的六邊形格子棋盤，給你一條路徑，滿足：
- 封閉：第一個格子和最後一個格子相同
- 簡單：除了第一個格子和最後一個相同外，路徑上沒有重複的格子。
- 無遮蔽：路徑上每一個格子都和至少一個不在路徑上且非內部的格子相鄰。
- 一個格子是內部的，若且唯若從它開始，在不經過這個路徑的情況下，只能到達有限個格子。
一個格子的分數是：
其中、 是給定的常數， 是它和第一個格子的最短距離。 這個路徑的疆域包含所有路徑上的格子和內部格子，求這個路徑的疆域中，所有格子的分數總和。
其實就是給你一個沒有洞的區域，問你這個區域有幾格（乘上
首先就是六邊形棋盤可以這樣對到直角座標上
這樣就等價可以六方位走的方格棋盤，然後我們就可以用直角座標做事了。
前兩個子題是給三角形，隨便畫一下就會發現它在六邊形棋盤是正三角形，或是在方格棋盤是等腰直角三角形且起點不是直角那個點。這兩個都可以得出格子數就是
小插曲是我不會算這個式子 XD，數學課有教過但我不記得，還好 APIO 可以上網查。
第三個子題很簡單，就是開一個
第四個我有想到是掃描線，但不知道為什麼沒過 QQ。
pB Rainforest Jumps
4 / 8 / 13 / 12 / 23 / 21 / 19 = 81
有
棵樹排成一列，每棵樹高度相異，當你在第 顆樹時，你可以跳到左邊比第一個比較高的樹或右邊第一個比較高的樹。有 筆詢問，每筆詢問求 從 中某個點跳到 中某個點最短距離是多少。
子題一就直接
然後有一個發現是，假設現在在
所以如果每個人的父節點都是它可以一步跳到的樹中比較矮的那個，可以蓋出一棵樹，這樣另一個也會是它的父節點。跳到比較高那棵的邊就當 back edge，注意到連續區間裡的 back edge 會一樣（簡稱跳段，會是一個子樹裡的某一側，可以用 Cartesian tree 想像一下），所以顯然固定起終點的話，在 back edge 一直跳，直到不能跳為止再開始走樹邊會是好的。
我本來的實作方法是找每個會跳到的點（簡稱跳點），然後數路徑上有幾個跳點，顯然不對因為跳點的數量不一定等於路徑上跳段的數量。正確作法是把 back edge 也拿去蓋一棵樹（簡稱跳樹 (?)），在上面跳完再到本來的樹（簡稱原樹）跳。
這樣可以過第 5 個子題。第 6 個子題是終點固定但起點不固定，起點必須是終點在原樹上的子孫，而且既然它是 Cartesian tree，一個子樹就是一個區間，所以可以維護每個點當終點時，起點的區間，然後再去跟詢問的區間取交集，然後顯然找深度最淺的點當起點就好了。
pC Road Closures
5 / 7 / 14 / 10 / 17 / 25 / 22 = 36
有一棵
個節點的樹，邊有邊權，拆掉一條邊的花費等於它的邊權，對於每個 ，求拆掉一些邊使得最大度數不超過 ，最小的總花費是多少。
第一個子題是星狀圖，直接排序然後加一加就好了。
可以樹 DP，每個點分別算往父節點的邊要留或不留的成本，這樣複雜度是
過程
（過程可能因為我太金魚腦導致順序錯亂）
APIO 可以用先寫好的 code，所以模板和 .vimrc 不用重打。老樣子開場先看完題目，pA 會做前三個子題、pB 和 pC 會前四個。
先寫 pA，然後我忘記
再回去寫 pA，發現是我沒 mod 後也順利讓分數達到了 93 分，想了一下後我想到了 pA 的第 4 個子題和 pB 的第 5 個子題。pA 的實作小麻煩，pB 也是。
我決定先寫 pB，因為我錯的那個想法有很多 case 要判（但還是錯的），很怕漏判 case，決定先過這個再想後面的，結果 Evaluating 很久，想說 judge 是不是掛了（其實這場裡面 judge 都偏久），果然沒過多久就出現公告，說現在 judge 大排長龍，要等一下。
等待時間決定先去寫好 pA，結果我傳 pA 後 pB 還沒 judge 完，而且還忽然所有 submission 都 rejudge，似乎是意外狀況，不過這也導致本來很長的 queue 變得超級長。
剩大概一個小時的時候我的 pA 和 pB 都還在 Evaluating，我決定檢查一下 pB，然後發現漏 case 再傳一次，再經過一段時間後公告說比賽時間延長 30 分鐘，我的 submission 已經有一些好了，但新傳的都還在等。
然後我發現我 pB 假解，趕快寫一個正確的傳上去，第一個假解 submission 已經 judge 完了，果然 0 分。
後來又等到剩 10 分鐘的時候，我忽然發現我忘記寫 pB 第 6 個子題。在發現我假解之前我就想到第 6 個子題怎麼選起點了，但因為我一直在想滿分解，就忘記有它了。
時間只剩 10 分鐘，這個子題值 21 分，一定要拿到。於是我使用最快的速度寫出 sparse table、算每個子樹的區間，在剩下 1 分鐘的時候 debug 完準備要傳，然後發現時間又延長 30 分鐘了（我的上一個 submission 都還沒 judge 好），我寫那麼急幹嘛。
在最後延長的 30 分鐘裡 judge 就恢復正常了，我也順利拿到 pB 的第 5 和 6 子題，但 pA 則是 WA，我想要試圖找出 bug 但沒有任何頭緒，然後比賽就結束了。
總結
分數 20 / 81 / 36
總分 137
排名 TWN 3 / 國際 51，銀牌
本來前 2.5 小時拿完 93 分時節奏都還不錯的，但後來 judge 掛掉節奏就整個亂掉，有夠衰。
算是打得還可以吧，該拿的分數都拿到了，只是 pA 掃描線那個沒拿到很可惜。（雖然我看別人是算面積，但應該沒有不能掃描線的道理ㄅ）
很幸運地撿到銀牌，銀牌線是 136，超危。我們二階結訓的時候還被威脅說 APIO 打太爛的話明年選國手就要算 APIO 成績，可能是我們去年全銅教授很生氣，聽起來超可怕，五月中才能知道國手，還好今年一金三銀二銅，我高中畢業前應該都安全了 (X)。
話說我 blog 已經半年沒發文了，我 Facebook 上有發零零散散的選訓營心得，本來想整理成一篇發在這裡，但時間過很久了就算了 (X)，可能等 IOI 完再發一篇今年資奧總心得ㄅ。