前言

高中會跑來 virtual ICPC 主要是因為要打 NPSC，不過網路上其實沒有什麼跟 NPSC 性質比較接近的比賽，我自己感覺 NPSC 會介於 OI 跟 ICPC 之間，不過既然賽制都是 ICPC 拿它來練一下默契跟習慣這樣的比賽應該也不是不行。

Virtual

開場高嘉泓從 A 開始讀，我從 L 開始讀，
一開始先看到 K 是水題，我上去寫之後高嘉泓他說 AB 都是互動題而且 A 是水題，

pK
給你櫃子裡的襪子，每堆有分左邊、右邊或不分邊，以及他所屬的種類。
一對襪子是由同一種類一隻左邊及一隻右邊組成，兩隻分別都能用不分邊的替代。
輸出要拿出多少隻襪子才能保證有湊對或者不可能。

不過 K 要判一點點小 case 然後我還判錯，總之後來還是做出來了，直接傳

00:13 pK AC +

寫的有點慢，小虧，
接下來就順利換高嘉泓上去寫 A，我往下讀，

pA
預先有一個比較密碼的程式，密碼由最多 20 位的 0-9A-Za-z 組成，
每個步驟的執行時間不同，
每次猜完你會知道有過沒過跟判斷的時間，
請用 2500 次以內猜到答案。

高嘉泓過程中出了一些小 bug，寫完之後丟上去

00:34 pA -1

吃了一個大大的 WA。
我一邊看一邊發現他有可能第一次就猜到，所以跟他講前面要是猜到要先 break，
修完之後再傳一次

00:36 pA -2

又吃了一個大大的 WA。
這時候我發現 G

pG
你有 $n$ 個已經用字典序排好的相異字串（總長 $\leq 10^6$）以及一個寬度為 $w$ 的螢幕，
你想要用最少的長度顯示他們，而規則是寬要被切成一欄一欄的樣子，兩欄之間有一個空白，
字串的順序必須依序是從第一欄由上而下、第二欄由上而下、依此類推。
$n,,w \leq 5000$

一看就是二分搜 DP $\mathcal O(nw \log n)$ 水題，但是實作超麻煩，不過我們目前也沒得開其他題所以我就先去寫 G，
高嘉泓在一旁 debug，
寫到一半又發現他又有地方沒判到，所以就再修了一下結果

00:34 pA -3

又吃了一個大大的 WA。

後來我順順的把 G 寫完，過程中出了一個迴圈變數打錯抓了一下下，然後就很順利的傳了

01:04 pG AC +

寫完我突然發現我看不懂高嘉泓的那個數學式，結果我們就抓到他應該要是大於才對，

01:06 pA AC +3

這時候接下來 J 有一堆隊伍開出來，D、H 也相當多，所以我們就先去做怪怪的 J，

pJ
給定一個長度為 $n$ 環遊世界路徑上的經度及緯度（最終回到起點），兩點之間的路徑是最短弧，
輸出是否有一條經線沒有被經過，如果有的輸出任何一組，必須以 .0 或 .5 結尾。
$2 \leq n \leq 1000$，相鄰點不會是同樣的點或對躓點，不會有北極或南極點。

看到之後一開始沒啥頭緒，想了一下我們發現緯度可以不用管，只要管經度相差走小的方向就好，
做著做著感覺是對的但是吃了一堆 WA，

01:25 pJ -1

01:33 pJ -2

之後高嘉泓 claim 他會 pH 兩個 $\log$ 的做法，

pH
有一個分成 $n$ 片的披薩，第 $i$ 片需要耐辣度 $a_i$ 才能吃，而吃完耐辣度也會上升 $a_i$，
一開始你可以亂吃任何一片，但接下來你就只能吃相鄰的那兩片。輸出全部吃完最小起始耐辣度。
$3 \leq n \leq 5 \cdot 10^5,\,0 \leq a_i \leq 10^{13}$

他跟我講之後我就跟他說可以先 sort 好壓掉一個，但是怎麼想都還是很難實作，
之後我就想到可以直接用 merge 的，不用用拆開的，我原本是想用 set 寫但他後來發現 DSU 也可以做到，
所以就先切給他寫然後我在旁邊慢慢 debug，
寫到一半的時候我決定把 J 的座標變換換成比較好寫的，避免出狀況，改了之後傳上去

02:03 pJ -3

所以我就決定等高嘉泓寫完請他重寫看看 J。
他寫完 H 之後傳上去

02:13 pH -1

傳上去之後他發現他有東西沒有取 $\max$，改了之後再傳

02:14 pH -2

然後就是我跟他 J、H 交替 debug，後來他先寫完了 J，傳上去之後還是

02:38 pJ -4

我後來抓到了一些他 H 怪怪的地方，傳了之後

02:42 pH -3

仔細再看看的時候發現他有一堆東西的計算順序是錯的，導致他其實根本沒有跟最大的限制取有效的 $\max$，抓到這個問題之後我們直接改，確定應該就是這個 bug 造成的問題之後，就直接傳上去了

02:47 pH AC +3

到這邊我們還是想不到 J 哪裡錯，所以就先去開很多人開出來的 D

pD
給定 $n$ 個格子，你要用最少的格子把他們圍住，滿足

• 用來圍住的格子以角角相鄰連通
• 被圍住的給定格子裡面形成一個以邊連通的有限面積區塊 $1 \leq n \leq 2 \cdot 10^5$

看到這題我們就直覺想到凸包，所以我就先去把凸包的模板打出來了，
問題是我們一直在想要怎麼圍住外面，我們想了角度的方法跟 DP 的方法，結果都不太可行，
後來高嘉泓突然想到
「把每個點四個邊的點都放進去做凸包不就完工了嗎」
我們就直接開寫了，寫到一半發現有一條斜率是 1 或 -1 的直線要特判，
所以要對原本的點砸凸包，然後我們就發現我們的凸包模板爛掉了。
緊急修理之後判完範測過了就直接傳，
「我覺得應該不止這個 case 欸，可是我們也想不到了」
「我也覺得我們有漏」

03:38 pD AC +

然後我們抱著應該不會過的精神去把 J 可以改的都改一改了，
在無計可施的情況下判了應該不會出現的北極南極點，

結果

04:10 pJ AC +4

？？？？？？
結果也不是因為北極點的關係，這個等等再說。

接下來能開的只有 F 計算幾何，L 可能是數學題跟 E，
L 我們唬爛一陣子就放棄了，所以去做了 E，

pE
給定兩個長度為 $n$ 的序列 $g,\,h$，互相是彼此的排列，
每一步驟可以交換任意兩個，條件是中間的元素都要嚴格比他們小。
輸出最少次數以及構造一組解，如果解太長只需要構造前 $2\cdot10^5$ 個步驟就好。
$1 \leq n \leq 3 \cdot 10^5,\, 1 \leq g_i,\,h_i \leq 10^9$

觀察之後就有很好的 greedy 可以做，不過最後高嘉泓寫實作寫到寫不完，就以六題作結了。

檢討

這場的問題就在我們實作太久了，除此之外只有模板問題，
所以需要多練幾場希望能穩一點。
至於 J 的地方是錯在我輸出的時候一開始會把 -0.5 輸成 0.5，
要特別注意負數

• 整數除法變大
• 小心 -0 會被弄錯
• 餘數是負的

剩下的部分就等補題篇再說ㄅ，我果然是不會 OI 也不會 ICPC 的笨蛋。