2021NPSC

今年 NPSC 變成線上的了orz
原本想說不是實體賽就有點懶得發文，只是想到還有一些值得紀錄的事情該記錄下來。

前言

因為去年帶的那個學弟今年不想打了，所以就從高一那邊抓一個看起來有料的進隊伍，想說從新血開始培養，不然竹中競程真的可能會下去= =;
我上個月把板中講義丟給他，比賽前三天我還得教他時間複雜度，坦白說我有點生氣，不過這不是這篇文的重點，只是因為他沒有準備所以我也沒辦法丟給他什麼題目。

第一小時

我們分配好切三半，我負責最後三題。
幸好 pH 跟 pI 題目都很易懂，所以我很快就讀完了，只是沒想法而已。

在看完 pG 後我覺得這題應該會是很可作的題目，就把其中一個隊友叫來一起想。起初想到的是先從最小的砍和最大的砍，但都有想到 hack 測資。突然想到會不會是直接砍最小的 $\frac{n}{2}$ 個數字就好，想一想發現超合理，看了一下記分板發現已經有兩三隊 AC 了，所以直接開寫。

pG AC 0/11
蠻幸運很快就開到這題，要是想快一點搞不好有機會首殺(?)，梗題就別要求這麼多好了。

燒雞開始。
發現到 pC 也已經有人 AC 了，就去看題目。隊友提出一個感覺很合理的從前面到後面 greedy，結果範測就 WA 掉了。
我開始胡思亂想，既然寫那麼快應該也是有很簡單的結論才對。如果把第一個位置按的次數叫做 $a$，第二個位置按的次數叫做 $b$，第三個叫做 $c$。那在 $N=3$ 的情況下我們可以列出這個線性方程組。
$$\begin{align*}
a+b &\equiv s_1\mod 2 \\
a+b+c &\equiv s_2\mod 2 \\
b+c &\equiv s_3\mod 2
\end{align*}$$
把他高斯消一消發現 $a, b, c$ 有唯一解，所以 $N\ge 3$ 的話必有解？

pC WA *1
把 $N=4$ 給消一消還是有解。

但是 $N=5$ 時突然就有了一個條件：$s_1+s_2+s_4+s_5\equiv 0\mod 2$。

第二小時

然後 $N=7, 9$ 都還是有解。可是感覺不會只有 $N=5$ 無解吧，後來隊友叫我把 $N\le 11$ 的爆搜看看，發現在 $N=2,5,8,11$ 才有可能無解。

把 $N=8$ 的拿去高斯消，發現條件是 $s_1+s_2+s_4+s_5+s_7+s_8\equiv 0\mod 2$。

至此結論已經出來了，但我根本不知道為啥前面幾隊可以寫這麼快。
pC AC 1/69

心態基本上已經爆炸了，此時的名次在超級無敵後面。
看到 pB, pF, pI 都已經有人開過了，聽完 pF 想說拓樸記數不是 NP 嗎？
所以就去開感覺比較可作的 pB 了。
這題就很正常，想法慢慢堆積到產生一個解。只是我太笨在想的過程中想太久，有些 claim 還被隊友 hack 掉。

第三小時

然後實作時才發現自己還有一堆 case 沒思考好，又花了一堆時間邊寫邊想，到很後面才終於過範測。幸好一發 AC。
pB AC 0/160

因為我們 pC 做太久，所以兩題線時我們在很後面，不過三題以上的不多，所以做出 pB 後我們就飛到比較上面了。
後來看到記分板上 pF 做出人數明顯多於 pI，所以就去想 pF 了。
因為我很確定一般圖算拓樸沒有好方法，所以肯定是那個 $\lt 1%$ 輸出 $0$ 在搞事。

高一那個學弟：「不能直接跑去計算有幾條嗎？」
我：「這樣複雜度肯定炸。」

第四小時

後來就是到處亂想，想辦法找到某個限制使得不滿足那個限制的話輸出 $0$，否則有了那個限制就會很好做。

但是找不到，後來突然想到高一學弟的那句話後發現：「喔靠北，直接 dfs 跑出 100 條就能 return 了啊」
被學弟徹底打爆了。
後來還有一些細節，比如在想拔掉一個點後 dfs 回來之後要怎麼把點加回去，用 set 帶一個 log 感覺就很爛。
後來是用 deque 把點直接 push_back，同時紀錄這層第一個走到的是誰來判斷有沒有全部走完。
pF TLE *1
喔，無解好像會炸掉，來判一下
pF AC 1/237

後來手上看起來比較可作的題目是 pD, pH, pI。
pD 我真的沒什麼想法。
pH 我在聽完題目時有想到 $dp_{i, j} := $ 有幾種 $s$ 的最後一個字元是從 $B$ 的第 $i$ 個字元來，且 $A$ 的前 $j$ 個字元是 $s$ 的子序列。可是在轉移時必須把 $B$ 之後的字元都遍歷過，然後感覺遇到重複字元的情況下很容易算到重複，尤其記分板沒人做這題，感覺處理重複的部份很難，所以先去做有人做的 pI 感覺就比較好。

賽後才知道這方向是對的，只要取最近一個字元就不會有重複，只看記分板就把這題丟掉是個超爛的抉擇。

尤其 pI 我也只想到二維表格 $B_{i, j}$ 代表區間 $[i,j]$ 有幾種相異數字，詢問 $[L,R]$ 相當於詢問 $B$ 從 $[L,L]$ 到 $[R,R]$ 的區間和。

這部份我只會用二維線段樹做。

第五小時

我想不到除了二維線段樹的作法，但這個作法複雜度很炸。
該怎麼辦？
繼續想 pH？直接開寫？
看了記分板後我還是決定唬爛看看寫這個。
結果寫了快一個小時連範測都沒過。

總結

4/517, rk10
這場 pB 真的就直接顯現了我在寫維護一堆東西的題目時常常都會整個亂掉或沒想好細節。
說是實作爛嗎？我也不確定算不算，因為我出的 bug 都是我想錯或者我沒想好，單純打錯字之類的都沒有。以前一直以為自己很擅長寫偏實作的題目，但那只是在 CF 偏實作而已，最近多 Vir 了幾場 OI 才發現 CF 的偏實作也只是小菜一碟，真的實作題我也是會一直沒想清楚然後寫很久。
想題目也想太慢，但這部份我不知道怎麼辦，只能說我太弱了。
最後的決策真的讓人很中風，因為自己已經有點落後了所以就會很想把前面隊伍開過的題目給開掉，結果就因此把可能做出來的題目給丟掉了。
高中最後一年 NPSC 就到這邊了，雖然很不負責的來說三年來每年名次都有進步，可是真的覺得自己應該還可以作到更好，比完之後心情也不是很好，與其說難過，比較像是滿滿的後悔，後悔自己賽前在混，後悔自己賽中想題目都在亂繞，後悔自己賽中決策。