0%

APIO 2021

又到了 APIO 了,去年因為疫情有延後,像今年一樣辦在 5 月才是正常的。本來應該要到師大比,但是剛好這陣子疫情爆發變成線上線上賽 QQ。這篇文大部分是在比賽完當天就寫的,但等 Open Contest 結束才會發。

這次每一題的子題都切得超級細,每題都有 7~8 個子題,只是前面的子題的分數都少得可憐 QQ。子題和限制就自己看題本啦。

題目·程式碼·Results

題目裡有中文

題目

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

棵樹排成一列,每棵樹高度相異,當你在第 顆樹時,你可以跳到左邊比第一個比較高的樹或右邊第一個比較高的樹。有 筆詢問,每筆詢問求 從 中某個點跳到 中某個點最短距離是多少。

子題一就直接 。然後可以照題目蓋一個 DAG,這樣複雜度是 ,可以一次拿到第 2 到 4 個子題。

然後有一個發現是,假設現在在 ,可以一步跳到 ,假設 ,那麼 也可以一步跳到 ,反之亦然。(其實就是 Cartesian tree)

所以如果每個人的父節點都是它可以一步跳到的樹中比較矮的那個,可以蓋出一棵樹,這樣另一個也會是它的父節點。跳到比較高那棵的邊就當 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,每個點分別算往父節點的邊要留或不留的成本,這樣複雜度是 ,可以過第 3 和 4 個子題,至於第 2 個子題,只要算 的就好了, 的話答案是邊權總和, 的話答案是 0。

過程

(過程可能因為我太金魚腦導致順序錯亂)

APIO 可以用先寫好的 code,所以模板和 .vimrc 不用重打。老樣子開場先看完題目,pA 會做前三個子題、pB 和 pC 會前四個。

先寫 pA,然後我忘記 所以就 WA,找不到為什麼,就先去寫 pB 了,pB 跟 pC 都滿順利就過了,其實我對樹 DP 會有小小的不安,因為常常寫得很亂,還好這次想法很清楚,沒出什麼 bug 就過了。

再回去寫 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 完再發一篇今年資奧總心得ㄅ。