[Virtual] JOI 本選 2021

, ,

初選快到了，看到雞塊在 vir JOI 本選也有點想試試看，
在這場之前有另一場是 JOI 本選 2022，因為忘記紀錄 submission 時間就等補題的時候再一起寫好了。

題目

  • pA Growing Vegetables is Fun 4
    你有一個長度為 $N$ 的菜園，每次你可以選擇某段 $[L,\,R]$ 都加 $1$，
    你的目標是反覆操作直到存在一個 $k$ 滿足 $[1,\,k]$ 嚴格遞增而 $[k + 1,\,N]$ 嚴格遞減。
    求最少次數。
    $N \leq 2 \times 10^5$。
    [40] $N \leq 2000$
    [60] 無其他限制。

  • pB Snowball
    平原上有 $N$ 顆雪球排成一列，第 $i$ 顆在 $X_i$，起初所有區間 $[a,\,a+1]$ 都有積雪。
    接下來氣象觀測站紀錄了 $Q$ 次風，第 $j$ 次的強度是 $W_j$，表示所有雪球的位置都 $+W_j$，
    過程中遇到的積雪每 $1$ 單位長度就會增加讓該顆雪球增加 $1$ 單位重量。
    一開始所有雪球重量都是 $0$，請在最後請輸出所有雪球的重量。
    $N,\,Q \leq 2 \times 10^5$。
    [33] $N,\,Q \leq 2000$
    [67] 無其他限制。

  • pC Group Photo
    給你一個 $[1,\,N]$ 的排列 $a$，你的目的是讓不斷交換相鄰兩個使得 $a_i + 2 < a_{i + 1}$。
    問最少次數。
    $3 \leq N \leq 5000$。
    [5] $N \leq 9$
    [7] $N \leq 20$
    [32] $N \leq 200$
    [20] $N \leq 800$
    [36] 無其他限制。

  • pD Robot
    給你一個張 $N$ 個點，$M$ 條邊的無向圖，邊有顏色 $C_i$。
    你要操作一個機器人從 $1$ 走到 $N$，但你只能告訴他要走什麼顏色，當機器人有多種選擇就會停止。
    每條邊都可以花 $P_i$ 塊錢改變成任意一種 $[1,\,M]$ 之間的顏色，問最小花費。
    $2 \leq N \leq 10^5,\,1 \leq M \leq 2 \times 10^5,\, 1 \leq C \leq M$。
    [34] $N \leq 1000,\,M \leq 2000$
    [24] $P_i = 1$
    [42] 無其他限制。

  • pE Dungeon 3
    有一個有 $N+1$ 間房間的地牢，從第 $i$ 間走到第 $i + 1$ 間需要花費體力 $A_i$，
    同時每間都有回復噴泉，第 $i$ 間可以花 $B_i$ 塊錢恢復 $1$ 點體力。
    有 $M$ 個挑戰者，第 $j$ 個想要從 $S_j$ 走到 $T_j$，體力上限是 $U_j$。
    你要對每個挑戰者輸出最小花費，或是輸出不可能。
    $1 \leq N,\,M,\,A_i,\,B_i \leq 2 \times 10^5,\, 1 \leq S_j < T_j \leq N + 1$。
    [11] $N,\,M,\, \leq 3000$
    [14] 全部 $U_j$ 相等。
    [31] $T_j = N + 1$
    [44] 無其他限制。

00:24

Score: 100/0/0/0/0
開場讀 A 就發現是雙指標裸題了，沒認真想導致出了一堆 bug，
例如說沒特判剩下一個元素、以為可以直接從 $[2,\,N - 1]$ 開始等等，
修完之後傳上去噴了 WA, RE, TLE 什麼都有，
看過一次 code 應該沒甚麼問題，結果是自己陣列開太小= =
實作超不穩，雖然 AC 了但 A 開的比我預想中慢。

00:46

Score: 100/100/0/0/0
接下來讀了 B、C，都沒想法。
B 甚至只有跟值域有關的複雜度，決定觀察更多。
畫了圖發現要維護的東西很多，但兩個雪球相間的積雪只會被他們兩個吃到，
然後就發現可以二分搜吃完的時間點，用前綴和直接算出答案。
看出這點真的看超久，被抓到不會觀察，燒雞。
傳上去 WA 手生測資直接發現我把二分搜弄成 $N$ 而不是 $Q$，笨死。

02:09

Score: 100/100/0/24/0
往下讀完 D、E，感覺 D 就是有點變化的最短路而已，但 C、E 都沒想法。
D 想了一個假解，我只考慮普通的最短路跟每個點的每種只出現 2 次的顏色，然後往下多跳一個點。
寫的超慢，因為要維護一堆東西，我偷懶用 map 存所以複雜度應該是 $O(M \log^2 N)$，傳上去只有過子題 2 24 分。
多 debug 幾次丟上去還是只有 24 分。

03:50

Score: 100/100/0/24/0
看了結果發現自己的做法沒有理由在帶權的時候爛掉，
重新驗了一次正確性的時候，發現自己假解，因為只考慮只出現 2 次的顏色不會是好的（剛好在不帶權底下是好的），
反而是，不管有多少個我們都要確定這件事，但複雜度會爆掉。
看過一遍之後觀察到了這個性質：對一個節點 $v$ 我們只要維護「最大、次大 → $v$ → 其他點」跟「其他點 → $v$ → 最大」會變好就好了。
這樣做等同建 4 倍的邊，所以複雜度還是好的。
然而傳上去的時候 WA，就決定跳題了。

04:39

Score: 100/100/100/24/0
C 不管怎麼看都感覺很難維護，觀察了大概一個小時。
03:12 的時候甚至想了一個 $O(N)$ 拓撲排序的假解，傳上去 WA 一片。
抓到假解之後拋棄了圖的想法，重新想了一次，發現合法解都是這樣構造的：

  • 往上 + 任意數字
  • 往下 - 1
    然後就意識到，他一定會是往上跳 → 往下走到底 → 往上跳 → 往下走到底不斷反覆，
    做完這個就很顯然的想到了 1D/1D 的 $O(N^2)$ DP，只要順便用均攤算逆序數對的 cost 就好了。
    原本以為 $5000 \times 5000$ int 陣列會 MLE 但他過了，好耶。

04:58

Score: 100/100/100/100/0
E 發現連子題 1 都不好做就先去看 D，努力 debug 之後發現我兩個解 WA 的測資剛好 disjoint XD
就決定拿舊解對拍，就看到自己的 sum 忘記初始化了，因為這個卡一小時，
當下真的是對自己的實作穩定度超氣，緊張的在最後兩分鐘傳上去，還好 AC 了。

Result

級距落在 400 ~ 499 的前 7 內。

心得

這場雖然結果算不錯，但根本就把我打回原形。
A 跟 D 的實作嚴重拖累整體進度（尤其是 D），經過一年我的實作穩定度根本沒有進步，燒雞。
B、C 則是抓到自己根本不會觀察，前四題根本沒有用到任何科技，主要都是觀察，
但我對觀察這部分真的很慘，如果這份出在初選我甚至只有 224 分。
最後是 E 的部分，其實子題 1 相當簡單，用單調隊列很快就做完了，可是我沒時間寫。
整體來說我的觀察跟實作能力真的弱到爆炸，但初選只剩一個禮拜了，感覺就要燒掉了。

可能這禮拜最多會再 vir 一次本選，希望能訓練到這部分。