NPSC 2022
*12/5 UPD：初賽 F 的部分翻完 submission 截圖才改成比較貼近事實的細節
最近有點多比賽還沒檢討，包含 NERC 2021-2022、SWERC 2021-2022 跟剛剛打的 IOI ‘15 Day 1，
不過 NPSC 算是繼區賽之後重要很多的大比賽，而且全國賽也快到了，趁著記憶新鮮來檢討一下。
初賽
賽前沒想到南一中今年會只剩我們這隊，所以就借不了電腦教室來打了，
初賽的策略是我先從最後一題開始看，然後高嘉泓從 A 開始看，
初賽可能沒有那麼刺激還有其實我有一點點忘了，所以下面可能會寫得簡略一點，
一開始我們先看到了 G，發現是一題裸的二維 DP，
做完兩個前綴和就寫掉了，
9 pG +
過了之後高嘉泓跟我說 D 是水題，所以他就先去寫 D，寫完不久就過了，
13 pD +
B 其實我有一點點忘記了，不過應該也是順順的寫就過了
29 pB +
之後高嘉泓去做了 C，他跟我講完想法我覺得很合理，結果寫完就在範測 WA 了，問題出在我們不知道前面有多的可以換得這件事之後，要怎麼用他們構造出更好的解，所以我看著芒果那一隊開出 F 之後就去看了 F，
F 一臉結論題的樣子，因為高嘉泓裝弱說他不會賽局，所以就由我這個數學笨蛋來開這題。
所以我就隨便打表亂耍笨就傳上去吃了一個大大的 WA
94 pF -1
推一推想說不太可能錯吧，所以我就把我的打表從二維變成三維，然後 claim 了另一個結論又吃了大大的 WA，
99 pF -2
然後我就做了一樣的事情，把表開成四維然後再 claim 了一下，覺得不放心再改了一次，
後來開成五維靜下心來好好推之後就想到了一個很棒的結論，但我不確定他到底是不是好的，所以就被友慫恿傳了兩個更大的 WA
109 pF -3
110 pF -4
最後就知道答案了可是我又更笨吃了一個 WA，
116 pF -5
119 pF +5
我們這時候想說我們 penalty 已經吃爆了，接下來就只能拚題數了，
（不過四題應該還是會進決賽吧）
PixelCat 那隊很早就開出我們沒做出來的 C，但我們想了一下又沒想到什麼就去想了接下來有人開出來的 A，
一開始我只有想到 $\frac 1 3$ 必定滿足的解，就是每 3 條劃 1 條直線，但這樣並不會過，
後來我把他推廣到 11 還是 13 個一組的方式，壓到理論最差 $2.2 \times 10^6$，
這樣差一點點就過了但我們加了一些剪枝就在隨機測資壓過去了，雖然是假解但我們在封版後一發過了，
186 pA +
後來我看了 E 有一點點東西但感覺離可做還差的很遠，所以就想全力做出下面也有些隊伍過的 C，
猜了很多解之後都發現有反例，是最後高嘉泓發現只要把剩下得都 greedy 換就會過，不用管能不能換，
我覺得有點唬爛可是下面的人都過了，應該可以相信砸個一次，然後砸下去就得到
230 pC +
高嘉泓好扯，orz。
團練
在初賽到決賽之間的這段時間，我們擠出了三個五小時打了幾場 ICPC，
基本上 code 在寫有時候是我跟高嘉泓各半，有時候是我佔了 70% 左右，
題數基本上都是還算可以接受的範圍，該開出來的大概少個一題左右，
很多時候 penalty 都是錯在實作出包，只有一兩次是假解，所以我們賽前擬定的策略就是我們不一定會輸題數，但我們很可能會輸 penalty，所以不能太亂傳。
題外話就是很多 ICPC 題目其實蠻酷的，雖然 codeforces 上面的難度有點爛掉。
決賽前
住宿
決賽剛好撞到段考，超怪，為什麼會有學校想要把段考辦在周末。
這年剛好競賽都撞到一些奇奇怪怪的東西，不過最後還是請到公假前一天考完搭火車上台北了，
到了台北之後火車誤點 19 分鐘，然後我們又坐特別晚的，所以九點半的時候我們才出月台，到處都沒東西可以吃了，
我突然想到麥當勞應該可以外帶而且很快，趕快找了最近的一家過去，
結果就是我不會三維計算幾何，所以我們就要再進北車繞到地下街再過去，到的時候還有十分鐘就關門，但我們還是順利買到了，就在捷運站外吃完去師大會館住宿。
該不會比賽已經開始然後我們從住宿就已經輸光了吧。
到站之後直接開始走錯路，還好一分鐘後就發現了，然後就多災多難的到了師大會館等他慢慢開收據之後進去住。
師大會館其實蠻簡陋的，不過價錢很低而且我們只是要去比賽其實還好，
晚上我睡覺的時候有被蚊子吵醒，不過我就直接覺得沒差啦睡覺比較重要所以就繼續睡了，早上起來我可能太緊張比鬧鐘還早起來，所以就想先寫出發前想到的 Codeforces 1753D The Beach，然後等高嘉泓起床。
他起床之後才說他晚上都沒睡好，然後我就心想搞不好我們真的從這時候就開始輸了，然後一邊一發過 The Beach。
賽前
走到會場其實蠻順利的，到了放完東西之後就看到一個人在等隊友的芒果，然後就跑去膜拜各路電神順便預測芒果穩前兩名。
測機的時候我們直接被抓到不會用 Sublime Text，所以就趕快找找看 DevC++ 有沒有可以用 C++17 跟 PBDS 的編譯器，最後是發現在 C:\\msys2\usr 裡面有（C:\\msys2\mingw64 跟 clang64 都是空的，到底怎麼回事），而且 judge 也很棒的不讓我們吃 CE，雖然我不知道我為啥可以兩題都 WA 超多次就是了。
我們測出來的速度大概是 $10^8$（based on rand()），但 PixelCat 說他們測出來 $3\cdot 10^8$，可能我比較笨。
決賽
剛拿到題目高嘉泓先看，我先改 compiler 跟打 default code，結果沒想到的是過了 10 分鐘都沒有人開任何一題，這時候高嘉泓跟我說 A 是一題數學，
pA
輸出 $\sum_{i=1}^N(\lceil \log_2 i\rceil \frac {N!}i) \mod M$，
$1 \leq T \leq 30000,\,\sum N \leq 10^{18},\,\sum M \leq 10^6$
我一看就發現 $N \geq 2M$ 是 $0$，然後維護前後綴階乘就好好的 $\mathcal O(M)$ 做完，很快寫完就拿到全場首殺了
17 pA +
不久有人開 H，所以我就去做因為他好像有點偏數學，
pH
給定 $\displaystyle f(x) = \begin{cases}\lfloor \frac x M \rfloor M & \text{if }x - \lfloor \frac x M \rfloor M \leq K\\ \lceil \frac x M \rceil M & \text{otherwise}\end{cases}$
構造長度為 $N$ 的兩個正整數序列 $a$ 使得 $f(\sum a_i) - \sum f(a_i)$ 最大跟最小。
$1 \leq N \leq 10^5,\,0 \leq K < M \leq 10^9,\,\sum a_i \leq 10^{18}$
完全沒頭緒，所以我就先亂 claim 了 $K = M -1$ 的時候兩個差值都是 0，
（如果你覺得怪怪的話沒關係，我沒有打錯，等等就知道了）
所以想了非常久，就構了幾組感覺很好的解就傳上去了，
58 pH -1
我就豪不猶豫的印出來 debug，然後我抓到我很有可能構到不想要的解，
另一邊高嘉泓說他會 D 了，
pD
給定 $a_1$ 顆紅球、$a_2$ 顆白球、$a_3$ 顆紅球、…、$a_N$ 顆的交替序列，
問有多少區間內的紅球跟白球與區間外相同。
$1 \leq N \leq 10^6,\,1 \leq a_i \leq 10^9$
所以我跟他就交替把兩題弄出來，
等他有點卡住之後我就直接上去改了另一個湊解的方法，
76 pH -2
這段時間真的很痛苦，尤其 H 是一題我摸不著頭緒的題目，然後高嘉泓似乎狀態也不太好，
比賽已經果一小時連兩題都沒開出來真的是有點慘，不過比賽的經驗告訴我心態要穩住，
H 後來應該是又改了一下下，結果一樣吃了大大的 WA。
96 pH -3
這一個半小時的狀況大概是我一直找不出哪裡爛掉，然後高嘉泓也一邊找不到他的 bug 在哪裡，
我原本提了我們兩個要不要換題目做或是跳題，但我後來想到了另一個一定會找的到作法，就是我就想到可以透過枚舉差多少個 $M$ 來做，應該會好很多，稍微推了一下式子就上去寫，結果還是做不出來，
111 pH -4
吃 WA，而且是瞬間就吃的那種，所以我很快就回去看我的式子發現到處都是錯誤，一大堆 max 打成 min 的，超雷= =
雖然改了之後，我還是沒改到致命的錯誤。
115 pH -5
另一個錯誤是我判斷可以多塞到多少的時候是算到 $M - K$，而不是 $M$，所以又仔細看過一次就發現我又算錯了，改完又傳了一次，
119 pH -6
然後我發現我構解沒改到，有夠蠢。
121 pH -7
之後我就發現了這個致命的錯誤：$K = M -1$ 的時候兩個差值不一定是 0，
我後來想如果我一開始沒有這個很有可能前面很早就會過了 ;w;
133 pH +7
我們直接從一題線頂變二題線底 XD
這時候我已經想說大概這場沒希望了，必須靠題數致勝，
結果我轉頭看向芒果那隊發現他們也只有兩顆氣球，趕快看計分板才發現全世界都在燒雞，我們還算沒有輸得太慘。
高嘉泓聲稱他做出 D 了，可是傳了之後沒過，
135 pD -1
後來是他發現他有漏 case，然後我一邊看著他在改一坨怪 code 一邊 debug，然後他又傳了一次
143 pD -2
這時候又有人過了 F，
pF
給定 $N \times M$ 的網格，總共會直線跟橫線切 $N \times M - 2$ 刀在格線上，
一開始整個是一大格，切過的格子會分裂，然後兩邊的格子內數字都會 +1，
給結果還原其中一種過程。
$2 \leq NM \leq 10^6$
一開始我看怎麼都只有用 set，在 judge 速度不太快然後 set 又很慢的情況下我不是很敢砸，
然後我突然想一想把他規成像括號的東西之後我就發現
「不是用單調隊列就做完了嗎」
然後我就很快寫完，最花時間的反而是驗解，然後我就傳了
158 pF +
做完我們直接起飛了，也太好笑
這時候高嘉泓還在燒 D，
我那時候趕快看了 D 就想到一個沒有 case 超級快的做法，就是把紅球當作 1、白球當作 -1，然後用雙指標跑紀錄路徑中遞增、遞減或持平跟持續的長度，然後再用加權總和跟連續性看有多少區間滿足。我覺得很乾淨所以我就直接把他的 D 搶過來重寫，
我不知道為什麼在找到一半可以燒一小段時間，不過改完一些小 bug 就很快過範測然後傳上去
189 pD +2
這時候心態跟節奏都回來了，然後接下來的選擇就是要做 B 或 E，
pB
有 $n$ 個人在打架，第 $i$ 個人的能力是 $a_i$，你每次可以找兩個人上去打，
能力比較大的人會贏，但他的能力會減少另一個人剩餘的能力，
輸出活著的最後一個人能力最大是多少？並且回溯一組解。
$1 \leq n \leq 100,\,1 \leq a_i \leq 10^5$
B 的部分高嘉泓一直燒雞先是提出了背包要 $\mathcal O(N V^2)$，
我其實那時候就想到把最大的人先拔出來，然後分成兩邊總和差最小，可以用 bitset 做到 $\mathcal O(\frac{N^2\max a_i}{32})$，
但我覺得有可能不會過，
E 的部分則是
pE
有一棵樹，你可以刪掉一條還存在著長度是質數的路徑上的邊，
有沒有辦法把整棵樹都拔光光？可以請回溯一組解。
$1 \leq T \leq 100,\,2 \leq N \leq 2\cdot 10^5$
很早就知道可以把質數拆成 $2,\,3$，就變成是一題實作樹 DP，簡單來講就是當成是 $dp_{i,\,j}$ 表示 $i$ 的子樹根還可以留一個長度為 $j (\leq 2)$ 的鍊，剩下有沒有辦法刪光光，推了 DP 之後發現可以判斷有沒有解，同時也能回溯，所以我們就直接去開 E 了，
我其實覺得這時候我應該專注開寫，不過我還是決定跟隊友驗然後慢慢寫，畢竟是大實作，
一開始很快就寫完可不可行了，然後就是量幾乎是兩倍然後思考量是四倍的回溯，
我一邊慢慢寫一邊想有沒有比較好的方式，最後還是實作出來了，
寫完驗解的時候燒掉，怎麼抓都抓不出來是哪條轉移爛掉，結果是高嘉泓把圖畫錯了。
確定沒問題就傳上去，結果
? E -1
隊友跟我看過了一次 code 說可能是我沒初始化，所以為了保險起見我就加上去之後就
? E -2
這時候比賽剩 10 分鐘了，我們幾乎是在跟時間賽跑，
我先很快複製一份 code 之後弄了最大值確定沒問題，然後再弄了隨機對拍，我自己估計應該是回溯的時候配對出問題，所以我就直接開 assert，然後果然在一筆 $N = 50$ 的地方出錯，
這時候大概剩下 7、8 分鐘了但我竟然忘記輸出測資，輸出完再對拍發現 $N < 50$ 的基本上沒有救，爆不出來那個 case，砸了 $N = 50$ 的隨機好幾筆才抓到，
我趕快請隊友念給我我畫圖，可是我想說這樣太慢了啊，畫完還要找，
所以我就直接把 dp 跟回溯輸出，然後找爆掉的點，然後看了一下畫完相鄰的點很快就發現我們少了一個判斷式，改完就直接傳了，
等 judge 的過程真的很緊張刺激，最終終於
294 E +2
然後我們就去傳了一個 G 的 WA，假裝有在做。
賽後
一開始我們以為我們慘了，結果才發現 5 題的少之又少，
我們估計我們大概是三到四名左右，因為我們應該是 5 題線 penalty 最高的，壓制性的那種。
題解的時候真的覺得自己卡在 H 卡太久了，不然應該可以再開個一題左右，整場敗筆大概就是我的 H，
然後抽獎頒獎的時候超好笑，
- 高嘉泓抽獎去轉那個指針，🉐
- 有人在 A 砸線段樹被公審，超好笑
- 頒獎不小心爆雷，這樣我們的 G submission 就不好玩了 qwq
最後是收在 Rk. 4，Penalty 1010，
最想不到的是竟然輸第三名只有輸 4 分鐘而已，怎麼會這樣…
檢討
基本上我初賽複賽都敗給偏數學的題目，我在這邊可能太久沒打 CF 猜到結論猜很慢，
可能需要稍微加強這小部分，被 H 雷到沒做出六題真的蠻慘的…
還有我應該相信我的 B 然後先趕快寫掉才對，
我真的需要多練點程式恢復以前的水準甚至更往上加強，不然我就等著全國賽被揍爛吧。
下一站就是全國賽了，希望高中競程人生的最後一年可以有好的成果。