2021 臺北市資訊學科能力競賽

###### tags: `Competitive Programming` <style> .lv1 { color: #e33d3d; font-weight: bold; } .lv2 { color: #e89a13; font-weight: bold; } .lv3 { color: #bfad0b; font-weight: bold; } .lv4 { color: #1ec93b; font-weight: bold; } </style> 2021 臺北市資訊學科能力競賽 === 去年三月參加資芽（我參加了兩次），那是我入坑競程的時間點，但真正比較認真練競賽大概是四個月前的事，所以這次心得文不只包含北市賽，也包含了賽前的心路歷程(?)，打完才發現寫太長，就當作是看小說，分段看完吧(X ## 趣事 1. BurnChickenLemma三人組全部三等獎，神默契www。在此立個願望，**明年我們三個全部成功進選訓，一起去師大玩**。 > 燒雞定理 = Sam + Foxyy + Gino，名稱來源：Burnside's Lemma 2. 一二三等獎的線切的意外乾淨，師大也太神。 3. 比賽的時候一直感覺到有股靈壓，尤其比賽過一小時，本來快炸掉瞬間冷靜下來進入撈分模式，出場翻轉播紀錄，果不其然又是 joy 在發功。 4. 下午跟建中團去玩桌遊。玩富饒之城被刺殺兩輪錢又被偷光，0 遊戲體驗 = ="，然後那隻聒狐又打翻飲料，不意外。 5. 玩碰撞機器人，Foxd 無情開電連續拿分，後來另一桌電神團也圍過來，一等三 aka DFS 大師 Alvin Chang 直接優超所有人把剩下的點全部撿走 <(\_ \_)>。 6. @鄭詠堯被 Foxdd 戳爆還一直被當狗狗，雖然有點同情但打架過程真的好好笑wwww ## 楔子最一開始是把目標放在二等獎，結果差一點如願，雖然很可惜，但也只能笑著接受了。定下這個目標大概是上學期期末吧，那時候被段考還有一堆死線迫近的報告壓得喘不過氣，作息大亂也讓身體也出了不少問題，跑診所醫院、諮商、吃藥，很痛苦，完全沒有活著的感覺。翻到別人的全國賽心得文，可以去新竹玩兩天，可以認識電神，可以享受優質的比賽，可以拿全國賽專屬的 T-shirt，很帥，很威風。另一方面是因為我不想再過那種被課業壓著過活的日子，我想真正全心投入自己喜歡的事，做我自己，哪怕學測已漸漸迫近，緩緩吞噬掉我的時間。想進全國賽的原因就這麼單純，沒有多麼神聖，也不需要。心之所向，身之所往，一場叛逆行旅就此開始。 ## 訓練開始練的時候是7月中，前面還在收資專的尾，另外還把高一的數專繼續延伸，跑去學FFT，包成學習歷程檔案，前後弄了兩個禮拜。最初就把競賽演算法列出來，看有什麼要學。結果別說大科技，光基礎演算法就學的七零八落，連 Dijkstra 都不會寫。想起年初參加 AA 競程，幾乎每場模擬賽倒數三名，被 dreamoon 說基礎功不夠，考慮很多 OJ，最後選擇從 CSES 開始刷，把基礎扎穩。後來學校暑輔開始，上了兩個禮拜發覺極度浪費時間，於是直接退出，每天去圖書館，早上讀學測 + 下午練競賽。剛開學一個月是我最焦慮的時候，那時候疫情升溫，一直在擔心北市賽會不會被取消，而且學弟請了防疫假，每天都能在家訓練。而我？白天昏昏沉沉地坐在教室，晚上還要推學測進度，幾乎沒有時間刷題。就算真的有空也早就疲憊不堪，沒力氣想題目。看著他一天一天變得更強，雖然有些欣慰，但更多的是實力離他越來越遠和追不上其他人的焦慮。市賽前一個月，我發覺我在學校的情況彷彿回到暑輔，一樣糟糕，一樣在浪費時間。思考很久，想從這糟糕的環境脫身，跟爸媽還有班導溝通很久，成功請到公假。我說服他們的理由是，第一次段考幾乎都是我自己讀還能維持班排一，證明我有顧好課業的能力，而且班導也知道我的實力並非與全國賽沾不上邊，是有機會的。一番抗衡後總算爭取到屬於自己的時間。公假的時候基本上就是補題，把之前 vir 的建中校內賽補掉，除了花枝遊戲還沒寫其他都補完了。再來就一直刷 CSES，繼續補我不會的東西。這時候因緣際會下接了校隊培訓的字串講師（其實我本來就有這個念頭），所以又開始學字串演算法。課表上面排定 Rolling Hash, KMP, Z Value, Suffix Array，就去翻了板中講義、建中講義、CF EDU，按順序把它們學掉，寫了一些題目後就開始準備簡報。題外話，我覺得最大的障礙大概是 Z Value 了吧，一直搞不懂估算 Z 值下界的那個做法，打轉了兩三天，某天早上睡醒的時候忽然想通了，現在反而覺得 Z 沒那麼難。本來要接續學 Trie 跟 AC 自動機的，但因為上課日快到不得不把時間拿去趕工簡報。誰也沒想到這次比賽我居然是被 Trie 卡掉，只能怪自己運氣太差、實力不夠吧。剛好培訓也開始了，又學了不少東西，SOS、插頭DP、差分約束、變形 Dijkstra、二分圖匹配、高斯消去。Wiwi 把 SOS 講的很好懂，先前完全看不懂這次一聽就會；差分約束資芽就已經學會了只是還沒寫過；終於搞懂 Dijkstra 的原理＆ k 短路徑的正確作法。唯獨二分圖匹配我完全沒搞懂，之後再重學。有堂課講整體二分、CDQ、其他資結，但我 claim 那些東西北市賽不會出現，我就算學了賽中一定刻不出來，剛好早上跟著打建中模競（燒慘），所以那堂課我在補模競的題（還沒補完），就沒跟著課堂進度。接著輪到我上字串，前一晚 rehearse 到簡報一半就因為太累直接去睡覺，導致後半堂課講的有點卡。我覺得我整體講的還不錯，但連續講話 3 小時頭真的很暈，喉嚨也燒掉。幸好看了醫生，隔兩天就恢復了。培訓倒數三天，被 Wiwi 餵了很多很難的題目，然後每個人要各自認領題目上來講做法，不過題目真的太難，除了電 Shaun 還有少部分人成功過關外，其他題目都幾乎是 Wiwi 親自上來講解。之後找時間再慢慢補掉吧。最後一天早上是模擬競賽，307／Rk.6，打得還不錯。**這場模擬賽對我來說很關鍵，我不只抓到了撈分的感覺，也對自己有了不少信心。** [**計分板連結**](https://rank.cms.wiwiho.me/) ![](https://i.imgur.com/fP2dnZI.png) 賽前一天一直在刷考古題，我很清楚自己底力不夠手感很容易斷，所以跟別人「賽前一天不做事／耍廢」的策略相反。晚上 9 點半就上床了，不過膀胱搞事，害我一直起來上廁所，過敏發作也讓我拖到 11 點半才入睡。隔天 6 點就起床，吃完早餐帶好東西就去師大報到了。 ## 賽中其實筆電試場意外的不錯。椅子高度很舒服，空間寬闊沒有壓迫感，重點是沒有嘈雜的鍵盤聲干擾思考，非常安靜，第一次打比賽能夠完全專注在題目上，感受不到其他人的存在。順帶一提 Ubuntu 用起來也很舒服，編譯跟執行速度特快。感受到師大的用心(?)，希望明年初選比賽環境也是這樣的規格。 ### 賽前 30 分鐘反正就開幕式 + 講解規則，肚子燒雞所以跑去廁所。接著吃了兩片薄荷巧克力補血糖，去飲水機補水，然後就定位等比賽開始。 ### 開場 — 1 hr／還沒睡醒開場花了些時間熟悉環境，開好 gedit、調設定、打編譯指令、打模板、...前後過了 10 分鐘才開題。題目可以參考 Shaun 的心得文： https://hackmd.io/lFPgW0mDTmW_wR1sTpEbhw?view 總之題目的 tag 大概是這樣： > **pA／** 上次 APCS P2 的既視感，看起來不難的語法題但我就是寫不出來的那種 > **pB／** 裸 trie > **pC／** 看起來是 DP 但我不會，不過 80 分很甜 > **pD／** 看不懂 > **pE／** 看不懂 again > **pF／** 圖著色問題，但這不是 NP 問題嗎 ...？看完題目，心涼了一截，trie 偏偏沒寫過，A 很煩躁，C 不會，D E 看不懂，F 更不在我學過的知識範圍內。想說 A 八成是簽到題，於是就開寫了。寫完以後範測炸開，才發現做法有問題，但我腦袋似乎還沒醒，一直亂改、亂試，好不容易範測對了，丟上去 01:02 pA 71 蛤，只過長方形的 subtask？然後我又繼續亂修、亂傳，中間還傳錯檔案 01:05 pA 0 01:07 pA 71 沒注意到已經過一小時了。 ### 1 hr — 1.5 hr／啟動撈分程序心態快要炸掉之際，大概是感受到 joy 的靈壓，我的理智線突然重新接回，pA 丟旁邊，想都不想就開始往下撈分。 pB 暴力比對 62 分 01:13 pB 62 pC 隨便 greedy 唬爛 32 分 01:21 pC 32 但其實一開始有 57 分，後來好像加強測資，所以被校正回歸。到這邊跑回去嘗試修 pA，結果沒成功。 01:34 pA 71 pD 想到要先用高斯消去弄出本來的數字，但還是搞不懂要拿這些數字幹嘛，範測也沒認真推，直接被我跳過。中途去上了廁所，也順便想了一下接下來的撈分順序。 ### 1.5 hr — 2.5 hr／品庠式打法重新讀 pE，總算搞懂在幹嘛，不過暫時觀察不出題目給的建邊方式有什麼關鍵點，只好先寫 37 分的 0/1 枚舉。 02:02 pE 37 這時候發現 pC 可以位元DP，馬上跳去寫，而且 5 分鐘就寫完了。 02:10 pC 80 然後發現我還沒動那題 output only，所以就跳去那題開始唬爛。先隨便寫了個 greedy 塗色，每次塗色掃過鄰點的顏色找 mex，丟上去 02:28 pF 30 只有 30 分？~~師大測資什麼時候這麼強了~~ 小改一下 code，但有改跟沒改一樣 02:34 pF 30 ### 2.5 hr — 3 hr／被 trie 送下去這時候發現不對勁，pB 應該要拿滿才對，可是我完全沒有寫過 trie，這時候開始有點慌了。匆匆跑去上廁所順便嘗試通靈 trie 的寫法，回來大概花了 10 分鐘，範測沒測丟上去，0分。 02:48 pB 0 測範測結果發現寫爛掉，徹底沒救的爛掉。這時想說剛剛暴力 $O(N^2 L) = 5 \times 10^9$ 都過了，感覺 rolling hash + 二分搜，順便加個剪枝（按照序列第一個數字分堆）應該有機會，我賭師大測資不會這麼強。先把分堆寫好丟上去， 02:54 pB 62 很棒，它是好的，接下來 rolling hash... 刻完 hash，剩兩分鐘... 刻完二分搜，剩兩秒鐘... Game Over. ## 比賽結果 ### Final Score／Rank :::success Total Score：**280**／Rank：**16**／**三等獎** [**計分板連結**](https://sorahisa.github.io/OI/DumpedRanks/nhspc2021_tpe/ranking/Ranking.html) ::: ![](https://i.imgur.com/ifWBB5d.png) ### Subtasks Gained > Tried and Accepted > Tried but in Vain > Supposed to Try / Easy Subtask **pA** 21／23／27／19／10 **pB** 29／33／38 **pC** 14／18／25／23／20 **pD** 27／27／46 **pE** 37／63 **pF** 10／10／10／10／10／10／10／10／10／10 ## 賽後比賽結束後，算一算分數只有 280，連一半都沒有。對照去年的分數分布，別說全國賽了，當下覺得自己連三等都沒有，甚至掉到佳作底。最後成績確認的時候，瞄到一堆人 300、400 多，完了，又開始慌了，越來越焦慮... 顫抖地拿起手機，打開計分板... 這計分板為什麼黃黃的？？？ > **280／Rk.16** 打這麼爛居然有三等獎？！出場後滿開心的，最後一年的北市賽，幸好不是佳作收尾。當初保底目標就是至少有前 20，算是滿足了心裡的部分願望。接下來細看分數分布，二等線 317，我只要 pB 有拿滿 = 318... ... 對，差一個子題為了弄校隊培訓，學了 KMP、Z、Suffix Array，偏偏沒有學好 trie 無奈後悔自責 ... 剛才的喜悅為負面情緒浸染，悲喜交雜，接下來下午到晚上我都是帶著這種複雜的情緒度過。幸好打完這篇心得的時候已經釋懷了。 ## 檢討 1. 前一小時又陷入糟糕的狀態，一直認為 pA 是簽到題，一直覺得大家都過了只剩我還卡住，沒好好想清楚就亂寫。幸好有調整回來。 > **現在意識到自己已經有一定的實力了，下次碰到這種情況可以合理相信「我做不出來的，大部分人也一定會被卡掉」。** 2. 基本功不夠，連 trie 都不會寫，這次剛好被戳中痛點。 > **底力不足，回頭看技能樹有哪些知識點還沒點到，就去把它點滿。吃大科技之前請先把底力練好。** 3. pD、pE 看了很久才看懂。pD 真的只是單純的高斯消去法，前兩天才刻過所以記憶猶新；pE 聽說是掃描線，我覺得只要好好靜下來思考就能想出正解。 > **讀題速度、精準度待加強，但除了刷題外我想不到其他特別加強這個的方法。** 4. pF 我拿了 1、2、9，但聽說 10 是二分圖，覺得很怪，八成是實作又有問題但我不知道 bug 在哪。 > **多嘗試唬爛的方法，能撈盡量撈(?)** . 我覺得最不應該發生的問題是 1.。 vir 了不少比賽，結果一不注意還是會陷入卡死的狀態。初選、資芽認證考、校內賽、這次市賽都是因為掉入情緒漩渦而失常。終於意識到這個問題的嚴重性，把它列入策略守則，每次比賽都要提醒自己不能卡死不能卡死不能卡死# ## It's not the end. 儘管與全國賽無緣，但我已經對拿了三等獎的自己很滿意了，而且最要好的另外兩個同伴也都拿了三等，滿開心的，雖然都差一點進全國XD。反正都知道問題在哪了，接下來就繼續練吧，明年還有初選，我是不會放棄的。然後文章開頭有提到， > 在此立個願望，**明年我們三個全部成功進選訓，一起去師大玩**。來發個祭品吧。 ```cpp= if (我沒進 TOI) exit(0); int ramen = 3; if (山姆有進 TOI) ramen++; if (Foxyy 有進 TOI) ramen++; if (山姆跟 Foxyy 都有進) ramen++; ``` **按 FB 貼文愛心就可以抽拉麵。** 其他表符都不算喔XD 喔然後 @Sam @Foxyy 如果你們兩個有進的話我會單獨請你們拉麵，當然前提是我也要有進。一起加油吧。回去練題囉 88。 :::danger **I shall return.** :::

Read more

AstroDX 使用教學

競賽／教學經歷

11/13 清大競程讀書會 題目分享

Cofiguration Files for Competitive Programming

11/13 清大競程讀書會題目分享