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})\mathrm{mod}M$。
$1\le T\le 30000,\sum N\le {10}^{18},\sum M\le {10}^6$

我一看就發現 $N\ge 2M$ 是 $0$，然後維護前後綴階乘就好好的 $\mathcal{O}(M)$ 做完，很快寫完就拿到全場首殺了

17 pA +

不久有人開 H，所以我就去做因為他好像有點偏數學，

pH
給定 ${\displaystyle f(x)=\{\begin{array}{ll}\lfloor \frac{x}{M}\rfloor M& \text{if }x-\lfloor \frac{x}{M}\rfloor M\le K\\ \lceil \frac{x}{M}\rceil M& \text{otherwise}\end{array}}$
構造長度為 $N$ 的兩個正整數序列 $a$ 使得 $f(\sum a_i)-\sum f(a_i)$ 最大跟最小。
$1\le N\le {10}^5,0\le K<M\le {10}^9,\sum a_i\le {10}^{18}$

完全沒頭緒，所以我就先亂 claim 了 $K=M-1$ 的時候兩個差值都是 0， （如果你覺得怪怪的話沒關係，我沒有打錯，等等就知道了） 所以想了非常久，就構了幾組感覺很好的解就傳上去了，

58 pH -1

我就豪不猶豫的印出來 debug，然後我抓到我很有可能構到不想要的解， 另一邊高嘉泓說他會 D 了，

pD
給定 $a_1$ 顆紅球、$a_2$ 顆白球、$a_3$ 顆紅球、…、$a_N$ 顆的交替序列， 問有多少區間內的紅球跟白球與區間外相同。
$1\le N\le {10}^6,1\le a_i\le {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\le NM\le {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\le n\le 100,1\le a_i\le {10}^5$

B 的部分高嘉泓一直燒雞先是提出了背包要 $\mathcal{O}(N{V}^2)$， 我其實那時候就想到把最大的人先拔出來，然後分成兩邊總和差最小，可以用 bitset 做到 $\mathcal{O}(\frac{N^{2}max{a}_i}{32})$，
但我覺得有可能不會過，

E 的部分則是

pE
有一棵樹，你可以刪掉一條還存在著長度是質數的路徑上的邊， 有沒有辦法把整棵樹都拔光光？可以請回溯一組解。
$1\le T\le 100,2\le N\le 2\cdot {10}^5$

很早就知道可以把質數拆成 $2,3$，就變成是一題實作樹 DP，簡單來講就是當成是 $d{p}_{i,j}$ 表示 $i$ 的子樹根還可以留一個長度為 $j(\le 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 然後先趕快寫掉才對， 我真的需要多練點程式恢復以前的水準甚至更往上加強，不然我就等著全國賽被揍爛吧。

下一站就是全國賽了，希望高中競程人生的最後一年可以有好的成果。