2021 資訊之芽一階 . 重返戰場 | 競程

03/06 ~ 04/03 第一階段前半

入芽

上一次來很多東西沒學會，想著要把基礎打好，於是今年再度打開粉專，填上報名表。很期待入芽考的說，沒想到因為人數爆滿，場地不夠所有人考試，去年來過的我今年直接免考當 $500$ 分算 wwww。不過題目我還是有看完，是都會寫沒錯，但我覺得三個小時內大概只能拿個 $200$ ~ $300$ 。

社交

去年課程結束之後，又在競程圈打滾了半年多，認識了不少人，因此剛開始上課的時候就是各種認親、膜拜，也很快找到同伴一起刷題、討論><（山姆超電），只不過目前看起來似乎只有我一個人是第二次來算法班的 OAO（可憐二階沒結業）。

上機作業

這幾堂課真的滿友善的，很多東西今年回來看也都突然變得很簡單，該補的知識點也都順利地補起來了。上課的時候還是有乖乖聽，回家以後上機題也沒有花太久時間寫，除了 IOI 2014 Game 那個想了爆幹久，我一直想開 $O(n^2)$ 空間蓋圖+砸並查集，但討人厭的是記憶體限制 $O(n)$ ，最後受不了上網查題解（譴責），才發現有那麼乾淨的做法，目前為止覺得最酷的題目之一 XD。

手寫作業

手寫作業的部分，因為一直想學 $\LaTeX$ 很久了（word 打數學公式還要用滑鼠一直點點點，難用程度堪比記事本），還好有用 HackMD 所以語法上的銜接沒有太大的問題，只是用之前還要載一堆 package、一堆排版的設定要打，好險有趕在第一次交作業之前搞定。之後的作業我就全部複製這次打好的模板，這東西真的比 word 好用太多了，對排版有嚴重障礙&強迫症的人真的是一大救星。

難到爆的 Greedy 證明

這幾次上課最大的收穫大概就是 greedy 的證明。去年我看課前影片的時候真的很吃力，一直暫停、重播、慢速，真的要手寫證明的時候才發現還是沒學懂，我那時候一直以為 greedy 的證明就只要先假設其他的解，然後很不嚴謹的 claim 說可以這邊弄一弄、換一換最後都可以換成原本的解，剛剛還回去翻我去年那連三分之一分數都拿不到的證明，嘔嘔嘔嘔嘔嘔快看不下去。

認真看完課前影片、例題之後，總算稍微理解證明的思路了，大概就是要先觀察出貪心解獨有的性質（其他解沒有的），然後根據這個性質對其他解執行一些替換，得到不比原來糟的解，接著證明這樣一直換下去最終必會得到貪心解（這也說明貪心做法是最好的）。只是我還是不會簡單扼要的說明，光第一小題就寫滿整整一頁=n= ...。

P.S. 今天被林柏瑄嘴砲「嫌寫證明麻煩就不要去啊」，啊我要是知道自己有一階前 15 的實力今年也不會想再來資芽吼=w=。

未來課程

接下來一階剩兩周分治&動態規劃，也是有一堆東西要補，期待我這兩周能好好聽懂上課講的東西，然後上課講的例題也能在認證考之前補完 OvO/（欠揍，去年到底在幹嘛）。

作業進度

Week 01 - 基礎資結上機：10/10 手寫：90/90

Week 02 - 複雜度、樹上機：04/04 手寫：120/120

Week 03 - 基礎圖論上機：06/06 手寫：85/85

Week 04 - 枚舉、二分/三分搜上機：06/06 手寫：115/115

Week 05 - Greedy 上機：06/06 手寫：125/125

04/10 ~ 04/23 第一階段後半

我切我切我切切切（week 06）

分治大概是整個一階最有收穫也最有成就感的課程了。

課程的部分，大概就那些經典題型重聽一次，但今年多加了超酷的東西—神仙分治，用超奇怪的分法，竟然可以在 O(n)的時間內找中位數，通靈出這作法的根本是神仙吧（還以為 Strassen 已經夠狂了）。

最滿意也最爽的大概是成功寫完上機吧，尤其是最後一題。去年不會寫，然後後面的課程講師也有給提示，但我聽到一半就跟不上而且也沒有任何頭緒，後面甚至直接忘記他講了什麼 www。反正就在紙上畫畫，先是想到分治但是是 $O(n^2)$ ，接著過了一兩天天，晚上洗澡的時候忽然通靈出單調性 $O(n)$ 。結果寫完以後一直 TLE 還跑去找 YP 求救 QQ，結果是自己中毒，不小心開了 1000000 個左右的 gp_hash_table，改成陣列就過了，而且常數還比線段樹小很多。總之 AC 的時候真的好爽，一直大吼大叫耍過動，總算對自己的能力有一點信心了。

順著這個思路，隔天沒多久就寫掉去年認證考 pA 了，大概就是先分 case，然後取總和就前綴和，取最大最小值就想辦法看出單調性。不過 YP 說這種純分治的題目幾乎現在的比賽不太會出，而且通常還會直接被各種資料結構如線段樹碾過去 QwQ。

我轉我轉我轉轉轉（week 07）

當天早上是校慶，前一個晚上趕工園遊會的東西+資芽作業弄到 3.才睡，隔天身體直接炸掉，擺攤的時候翹班去睡覺（1510 的抱歉 QAQ），上課的時候差點陣亡，慶幸的是內容（基礎 DP）夠簡單，不敢趴下來於是就開啟省電/半休眠模式刷水題。

還是有稍微聽最後面的區間 DP，但最後一個例題聽不太懂跑去戳講師，那位講師今年才加入(?)但他講話好有趣ㄛ，資芽的每個講師都好酷又好電> <。

我燒我燒我燒燒燒（認證考前一天）

明天就是認證考了，所以整理一下給自己看的 checklist：

賽前

考前禁刷題/複習簡報
10:3 0上床睡覺
08:3 0起床
記得帶 codebook 不過應該是用不到
記得帶 pocky/小餅乾
午休 20 分鐘

賽中 7. 先看題目，記錄子題分數 8. 5 分鐘打好模板 9. 評估解題時間/排好解題順序 10. 1.5 小時補充一次糖分 11. 要打任何一個字元前，先確定想法是對的/測過範測 12. 送出一個 submission 就去廁所 13. 停損點很重要，心態不要燒雞，當一個沒有感情的打字機

目標

拿到 100 分
前 15 名就好

作業進度

Week 06 - 分治上機：06/06 手寫：__/__

Week 07 - 基礎動態規劃上機：07/07 手寫：這週沒有> <

04/24 第一階段認證考

首先是恭喜 wiwi 當上國手

接著，誠心預祝那些在捷運上盜我帳號的人，以及留言膜拜的人，明年初選滿滿 AC，撈分都能撈滿，順利進選訓且不會壓線。如果已經有一階的，明年順利進二階。你們都穩了

。

好滴，感謝 & 祝福的話說完了。接下來直接上題目 OvO。

題目

Problem A - (100/100)

現在有一個神秘的黑盒子，芽芽要對它進行 $N$ 次操作。

把一顆編號 x 的球放進盒子。
把盒中最早放進去的球拿出來。
把盒中最晚放進去的球拿出來。
把盒中編號最大的球拿出來。

保證盒中不會出現相同編號的球，請在操作 2、3、4 之後輸出取出的球的編號。

Constraint: $N \leq 200000$

Problem B - (100/100)

給定一個常數 $C$ ，現有 $N$ 條線段，每條線段的權重為 ( $C$ -該線段的右界)。
請選出一些互不重疊線段，使得它們的權重和最大。

Constraint: $N \leq 500000, C \leq 10^9$

Problem C - (25/100)

有兩個正整數序列 $(a_1, a_2, ...a_n), (b_1, b_2, ...b_m)$ 。

從第 0 秒開始，當現在時間為 $t$ 時，第 $a_{t \bmod n}$ 個元素會被減去 $b_{t \bmod m}$ 。
求最快經過多久時間，序列 $\langle a_n \rangle$ 便會出現非正整數的元素。

Constraint: $1 \leq N, M \leq 100000, 1 \leq a_i, b_i \leq 1e12$
Subtasks:
- (10) $m = 1$
- (15) $n \bmod m = 0$
- (50) $gcd(n, m) = 1$
- (25) No other constraints

Problem D - (100/100)

此題為互動題。
題目事先定義好一個整數類別，但只支援加法和乘法操作，且不會有 overflow 的問題。
要求實作一個給定的函式，傳入參數 $r$ 和 $n$ ，並回傳首項為 $1$ ，公比為 $r$ 的等比級數的第 $n$ 項。
另外系統會呼叫 $t$ 次該函式。

Constraint: $1 \leq t \leq 20000, 1 \leq n \leq 1e18$

Problem E - (100/100)

現有一棵大小為 N 的樹，給定一個數 x。
請在這棵樹上找出一個點集，滿足此點集連通，且將此點集從這棵樹去除後，剩餘的樹大小皆不超過 [N/x]，
並且要使該點集大小越小越好。
另外，如果找出來的點集大小並非最小，還是可以獲得一些分數（有個算分公式但我忘了）。

Constraint: $1 \leq N \leq 200000, 2 \leq x \leq N$
Subtasks:
- (20) $x = 2, N \leq 2000$
- (30) $x = 2$
- (30) $N \leq 2000$
- (20) No other constraints

考試過程

我不敢寫比賽不然會被波路特石打爆，他一直強調這是考試不是比賽。

開場就老樣子，讀完題目，把子題分數記在紙上。
接著花了 5 分鐘打模板順便思考解題順序。
pA 是裡面最簡單的題目，而且我社內賽還有出過一模一樣的題目。
只花了 5 分鐘就讓它變綠燈。

(00:20 100/500)

pB greedy 不敢亂猜答案，怕 WA 了以後影響心情。
pC 看起來不是那種一下子就可以寫掉的。
pD 知道作法跟快速冪一樣，但那是互動題感覺有點麻煩。
目前看起來最可做的就是 pE。在紙上推一下後發現我除了 50 分樹重心以外的 case 都想不到怎麼構造最佳解，於是決定先拿 50 分。

(00:40 150/500)

這時決定去上個廁所，回來以後想到，因為找樹重心會順便計算每個子樹大小，乾脆 $x$ 不是 2 的 case 就一口氣把所有子樹太大的節點全部輸出。本來以為頂多多拿個 10 幾分，結果 verdict 出來... 83.77，酷欸隨便做就有 80，感覺拿得差不多了，這題就被我放著。

(00:55 183.77/500)

想了一下決定先做 pD，光看懂實作細節就花了大概 10 分鐘，然後因為比較膽小所以就比較笨地分偶數跟奇數的 case。因為題本上面寫「乘法運算常數會很大請小心使用」，寫完本來還以為過不了大測資，準備開始寫預處理，沒想到居然 AC 了，有點小開心。

(01:30 283.77/500)

這時候可以比較放心的猜 pB 的解了，想了一下，咦啊這不就先選越早結束的越好嗎，並且滿足度掉到負的就不要拿。隨便弄了幾個測資，感覺沒什麼問題，花了 10 分鐘寫完丟上去還真的是對的，剛剛一個小時前講師還在前面恐嚇說有加強測資，還說要 WA 的同學重新想想看，然後我被嚇到前半場不敢戳這題。

(01:45 383.77/500)

出去上個廁所，上到一半盯著眼前的磁磚，中心顏色比較深，周圍比較淺，嗯... 顏色比較深的那個感覺有點重心的 fu 欸。突然，砰！馬上想到正解。剛剛 83.77 分是隨便抓一個節點當根，因為可能抓到葉子，自然就會多拔掉一些無關緊要的點，把重心當根正好可以解決這個問題，於是過了 15 分鐘 4 AC 到手。

(02:00 400/500)

再來剩 pC ，大測資卡住所以先把比較簡單的寫掉。

(02:15 425/500)

接著就是整場比賽最大敗筆。大概過 5 分鐘知道可以用倍增法，但我就卡在不知道怎麼用倍增法跳著維護每個 $a_i$ 會吃到的數字的前綴和，我只會維護 $a_i$ 在第 $2^i$ 輪會吃到哪個數字。然後看到 subtask 3 那誘人的分數，只要重新 build $b$ 陣列再套個前綴和二分搜就好了。被初選帶壞的我總是一直想著撈分而逃避思考滿分解，結果二分搜不知道哪裡寫爛，找不到 bug，然後就這樣燒掉了 RRRRRRRRRR

考試結果

分數：425/500

名次：3

@邱翊均破台，超電

@李政遠 430，把我打爆

今年題目難度跟去年差好多。
去年墊底今年打得還不錯有點爽，不過我還是很弱/還有很多要學。
很不滿意最後一個小時的表現。賽後想到其實只要再多維護一個 tag 就好，就可以用倍增寫掉那題。提醒自己以後剩下一題，而且對滿分解有想法的時候就好好把它想清楚，不要一直想著撈分。這次是連停損點都沒設，想都沒想就把眼光縮小在子題上面。

吃晚餐的時候，聽 YP 還有波路特石分享一些經驗 & 建議。感想很多，不過我暫時不想寫出來，不然又變成一篇滿滿 flag 卻又一點都不實際的廢雞湯文。