[Online Mirror] BOI 2022

到底是誰會在段考前花 10 個小時燒雞阿= =

這篇就不防雷了，點進來的大概都是有打過／不想打的吧。

Day 1

開場先讀題，

• pA art [3s, 512 MB, Communication]
  Judge 有一個 $1$ 到 $N$ 的 permutation，
  你可以猜 $4000$ 次，Judge 會回傳逆序數對的數量，
  最後你要回傳那個 permutation 的答案。
  $1 \leq N \leq 4000$
  [5] $N \leq 6$
  [15] $N \leq 40$
  [15] $N \leq 250$
  [15] $N \leq 444$
  [20] $N \leq 2000$
  [30] 無額外限制

Day 1 最大的敗筆就在這裡出現了，
這題我看錯意思，甚至連範例都不知道為什麼可以想錯，
總之這題我以為他回傳的是「你低估排名」的數量，
感覺很難，根本就做不出來。

• pB events [1s, 512 MB]
  有 $N$ 個事件，每個事件有起始時間點跟結束時間點 $S_i,\,E_i$，
  你可以切換到另一個事件的條件是當下事件 $i$ 結束的瞬間，要切換到的事件 $j$ 還在進行，也就是 $S_j \leq E_i \leq E_j$。
  $Q$ 筆詢問從第 $s_i$ 號事件切換到第 $e_i$ 號事件最少需要切幾次，沒辦法切到輸出 -1。
  $1 \leq N,\,Q \leq 10^5,\,1 \leq S_i \leq E_i \leq 10^9,\,1 \leq s_i \leq e_i \leq N$
  [10] 每個事件最多能切換到 $1$ 個事件
  [10] $N \leq 1000,\,Q \leq 100$
  [15] $N \leq 5000$
  [15] $Q \leq 100$
  [20] 沒有任何事件被其他事件完全包含
  [30] 無額外限制

一開始看沒什麼想法，大概覺得 subtask 5 可能有些幫助，

• pC vault [4s, 512 MB]
  有一大堆權重是 $1$ 的物品，體積是 $i$ 的有 $A_i$ 個，體積介於 $-M$ 到 $M$ 之間，問剛好湊到體積 $L$ 的最大權重。
  $1 \leq M \leq 300,\,0 \leq A_i \leq 10^{12},\,10^{-18} \leq L \leq 10^{18}$
  [5] $M,\, A_i \leq 50$
  [15] $M,\, A_i \leq 100$
  [20] $M \leq 30$
  [20] $M \leq 50$
  [20] $M \leq 100$
  [20] 無額外限制
  在 Subtask 3 ~ 6 中，如果解出 $i \leq 0,\,A_i = 0$ 的所有測資可以得到 50% 的分數。

subtask 1、2 看起來就是經典的背包，
然後其他的部分感覺沒有很有想法，值域大到根本不知道怎麼做。

所以接下來做題的順序大概就會是 B $\rightarrow$ A $\rightarrow$ C，

後來想了一下以為可以撈到 A 的一些子題，但一直弄來弄去之後發現假解了，就乖乖回去做 B。

01:00

$\newline$

B 後來把起終點反過來之後，歸出來跟某場我遇到的題目很像，
觀察到一個事件結尾在走 $k$ 步可以到達的地方剛好是一個連續區間，所以就直接開刻用 sparse table 做倍增處理查詢，
複雜度是 $\mathcal O(N \log^2 N + Q \log^2 N)$，看到 $N,\,Q$ 都只有 $10^5$ 就放心開刻了，
當下沒有想到稍微判一下往後只會是一個區間，然後往前可以單純倍增就好，這樣可以壓掉一個 $\log$。
過程中 bug 出超多，光實作就花了整整一小時。

01:59 B 100

$\newline$

BOI judge 超快，cms 上編譯完執行兩秒就拿到 AC 的 verdict 了，
（賽後重新傳一次看時限之後，每筆測資印象中不超過 0.2s，超級快 OAO）

接下來 A 還是沒想法，就去做做看 C，
做一做之後想 Claim 我只要先 greedy 的拿比例最好的，然後在空間差 $M$ 以下的時候，每個物品保留 $\pm M$ 個的改變彈性，然後做容量是 $M^2$ 的背包就好。
理由是你會發現最佳解跟這邊差的東西真的不多，所以稍微構一下如果都用大的湊，把他們都編成總體積增加一組一組，就不會用超過 $M$ 個，小的東西雖然可能用到很多，但相對的他的彈性就變很大，所以我相信可以控制在這個範圍內。
再來就是我猜最終複雜度可能就是這樣。

先刻了一個只有正的 + 基礎背包傳上去，

02:25 C 0

$\newline$

吃了 TLE，結果是自己取 $\min$ 有一個取錯位置。

確定是好的之後，原本打算要開始寫單調隊列優化，不過用二進位分的方法太好寫了，而且 BOI 的 judge 好像很快，就決定直接帶一個 $\log$。

02:32 C 40

$\newline$

接下來就是要去想負體積要怎麼處理，把剛剛的 greedy 部分擴展一下就可以發現直接先拿，然後把他的權重當 $-1$ 就好。

大概在 02:48 就寫完了，但是差了好幾個 bug，第一個是因為有正有負弄錯 id，後來重推一次式子之後還是燒雞，最後是把 DP 表格印出來才發現自己戳出陣列= =

03:19 C 100

$\newline$

為什麼我不要出 bug 就好好印出表格來 debug 啊= =

剛剛有提到我 A 看錯，所以以為他是最難的題目，
所以就先寫了 next_permutation。

03:22 A 5

$\newline$

後來想了很久還是想不到要怎麼做，所以在 4 小時的時候決定開始寫剛剛想到的部分分。

寫了很久發現怎麼跑起來都怪怪的，一開始真的是我自己出 bug，但到了後來我修掉之後還是怎麼跑都怪怪的，去翻了 sample grader 才發現：

04:27

$\newline$

他是回傳逆序數對欸= =
當下很氣自己為什麼對實作一直都很懶惰，如果我早一點喇分就會發現我自己理解錯題目了。

不過也只能好好打完，所以我就寫了一個 bubble sort 傳上去

04:38 A 20

原本要砸 sort 的，但不知道為什麼我的 comparsion function 一直吃 RE，
我猜可能是戳到什麼我沒看過的 UB 了，所以就沒救了。

Result

							Sum
A art	5	15	15	15	20	30	20
B events	10	10	15	15	20	30	100
C vault	5	15	20	20	20	20	100
Score							220

真的超笨欸= =
Day 1 最難題 C 做出來的小方塊竟然可以看錯 A 白白丟掉自己的分數

Day 2

開場還是照樣先讀題，

• pA communication [5ms per test, 8 MB, Communication]
  你要傳輸一個介於 $1$ 到 $N$ 的數字，你最多可以傳 $250$ 個 $0$ 或 $1$。
  然而通訊有很嚴重的干擾，當你傳出去之後，訊息有可能會是錯的。
  不過幸運的是，傳輸方可以知道自己這次傳的是對的還是錯的，而相鄰兩次傳輸至少有一次是對的。
  接收方只能一個一個位元接收，而且不能接收過頭。
  但是接收方可以猜兩種可能，只要其中一個對了就可以得到 Accepted。
  $1 \leq N \leq 10^9$
  [15] $N = 3$
  [85] 無額外限制，假設你最大傳輸的次數是 $w$，你在這個子題裡的得分 $S$ 是： $$S = \begin{cases}85 & w \leq 100\\85 - 2(w - 100) & 100 < w \leq 110\\65 - (w - 110) & 110 < w \leq 140\\35 - \frac 1 3(w - 140) & 140 < w \leq 200\\15 - \frac 1 5(w - 200) & 200 < w \leq 250\end{cases}$$

超怪題，大概是不可做。

• pB island [1s, 512 MB]
  給你一張 $N$ 點 $M$ 邊的圖，點 $i$ 帶正權 $s_i$，第 $i$ 個點一開始是塗成第 $i$ 種顏色。
  一個點 $u$ 可以把某個相鄰的點 $v$ 塗成 $u$ 的顏色若且唯若整張圖中跟 $u$ 塗同一個顏色的總權重 $\geq s_j$。
  對每個點決定可不可以把整張圖都塗成跟他一樣顏色。
  $1 \leq N \leq 2 \times 10^5,\,0 \leq M \leq 2 \times 10^5,\,1 \leq s_i \leq 10^9$
  [10] $N,\,M \leq 2000$
  [15] 圖是一棵樹且以 $1$ 定根之後所有點的所有小孩的下標及權重皆大於祖先
  [15] 圖是一條鍊
  [30] $s_i$ 最多只有 $10$ 種取值
  [30] 無額外限制

一開始看沒什麼想法，感覺也是難題但可能有好性質。

• pC passes [2s, 1024 MB]
  有 $G$ 團人要登機，總共有 $N$ 個位置，
  你可以決定每團人登機的先後順序以及每個人要從前面還是後面上，但不能決定同一團上去的順序（他會是一個隨機的排列）。
  問走過已經坐人位置次數的期望值。
  $1 \leq G \leq 15,\,1 \leq N \leq 10^5$
  [5] $G = 1$
  [25] $G \leq 7,\,N \leq 1000$
  [30] $G \leq 10,\,N \leq 10000$
  [40] 無額外限制

推一下期望值的 DP 式就可以發現有 $\mathcal O(G^2N + 2^GN)$ 的作法，應該可以拿到 60 分。

中間實作很卡，但基本上就沒什麼好講的了。

01:07 C 60

$\newline$

後來大概就可以想到是二分或三分搜找最低 cost 了，但要對什麼二分搜我一直都想不到，後來甚至是根本沒有靜下來好好推而在打表亂猜，雖然打表猜本身的策略應該沒有很大，但我在這邊浪費太多時間（大概快半小時）了，大概是這場最大的問題。

後來切去嘗試 CTF A 但 BOI 好像超會魔改 cms，就丟掉 A 了。

這時候我就先去做 B，觀察到如果一個點不能讓所有點都塗成他的顏色，那在這過程中他走過且比他大的人就不可能，但似乎用這個剪枝根本不可能會過，

後來決定先寫暴力跟樹的 case，一條鍊我覺得是要單調隊列但我沒觀察到關鍵的性質，反倒是我覺得只有 10 種取值的子題可能很有幫助。

03:01 B 10

03:09 B 10

$\newline$

後來觀察到最大的一定可以，然後次大的就是把比他小的都合併之後，看能不能打敗一個比他大的，第三小的就是把比他小的都合併之後，看能不能打敗一個最大的或打敗一個第二大而且他可以打敗最大的那個，依此類推。
所以這樣就可以用 $\mathcal O(10N)$ DFS 做掉，當時還沒想到要怎麼做滿分就先寫了。

03:47 B 10

03:51 B 10

$\newline$

傳上去還是只有過暴力，其他 TLE，所以就回去 debug 之後還是沒找到，就決定去跑 Testing，Testing 跑出來沒問題，
結果是我自己傳錯檔案了= =

03:56 B 40

$\newline$

後來滿分解的部分就是把 DFS 換成 DSU，先 sort 按照權重順著做然後 roll back 的時候一邊記錄整個連通塊是不是好的。
其實賽後看的時候發現我的 code 裡面有很多東西是我當下沒有觀察到但寫對的，例如說 dsu 上面應該要判一些 case 但實際上多看幾下就會發現這些 case 會因為答案的性質而不用多判。
實作稍微有一點點麻煩所以寫了一段時間，而且我又傳錯一次檔案了，傳對之後就拿到 AC 了。

04:32 B 100

$\newline$

A 到底是什麼大難題，根本連 $N = 3$ 都不會。

Result

							Sum
A communication	15	85					0
B island	10	15	15	30	30		100
C passes	5	15	30	40			60
Score							160

這場除了 C 一直亂猜，其他都正常很多了。

Final Result

							Sum
Day 1 A art	5	15	15	15	20	30	20
Day 1 B events	10	10	15	15	20	30	100
Day 1 C vault	5	15	20	20	20	20	100
Day 2 A communication	15	85					0
Day 2 B island	10	15	15	30	30		100
Day 2 C passes	5	15	30	40			60
Score							380

Online Mirror Rank: 7
Official Rank: 6, 壓線金牌

檢討

基本上 Day 1 的問題比較大，看錯題目這件事不應該發生，而且我對實作的懶惰真的會害到我自己，我可能要著手去想怎麼去勇敢的面對實作的問題；Day 2 的部分最大的問題就在我一直在亂猜沒有靜下心好好想想，至少這半小時我可能可以多拿 A 15、或早點做出 B 都會好一些，另外的一個小問題是我會傳錯檔案，或許今年二模那邊暴力沒過就是因為傳錯檔案吧。

整體來說是打得還可以啦，但真的需要再加強這些部分。
倒是這樣我對明年模考會有點怕我會再燒雞，因為我感覺我比較擅長五小時三題的時間分配，模考五小時四題基本上就不能出太大的失誤、實作的速度也不能像現在一樣慢慢實作慢慢找 bug。
每次檢討到最後都在噴自己實作但一直都沒改善，這個暑假我來好好思考這個問題好了。