# 序
大家好我是DnDA，我是一個高二下快結束才開始學C++的菜鳥，最近拿到了APCS檢定的觀念4級實作5級。
10個月前，我從完全沒有C++基礎開始學競程，而我的第一個目標就是在APCS中取得好成績。不過，當我想要了解它的難度、該如何準備等等的資訊時，我只在網路上找到各種補習班以招生為目的寫的文章，其中許多內容也令人懷疑。我又用不同的關鍵字搜尋，希望能找到學生以親身經驗寫的心得文，可是各路大神似乎都不認為考APCS是需要經驗傳承的活動，所有寫的都是全國賽、初選，甚至模考等對當時的我太過夢幻的東西。我還記得當時那個什麼都不知道、對什麼都沒概念的我。
因為這樣，這篇文章誕生了。我希望能藉由分享我身為一個初學者的經驗，來讓未來對競程有興趣的人有一份比較沒那麼遙遠的文章可以參考。同時，這也是一份給我自己的紀錄，讓我可以在未來某一天覺得有些迷茫時找回自己的初心。具體來說，**我的coding歷程** 這大段主要紀錄事件，而 **Q&A** 則存放我的一些感想。
不過，有個尷尬的點。我在學競程初期時，有很長一段時間把目標放在APCS實作五級上，我本來預計的感想也很多跟這個檢定相關。然而，聽說APCS要在今年(2025)年中大改版，不少經驗可能無法適用新制，因此篇幅就變得簡短許多。
不管怎樣，預祝看到這篇文章的讀者可以讀得開心並有所收穫。
# 我的coding歷程
## 第一次想好好學C++
我還記得，那天是2024年3月1日，高二下的我剛結束一場又一場的雀魂，被放學的鐘聲喚回現實世界。我幾乎每天都沉浸在電動中，從早上八點第一節課玩到五點放學。那天，可能算是某種新月新希望，我心裡突然有個想法：再過不久我就要高三、要考學測了，我是不是該戒電動了?
根據我之前戒電動的經驗，突然把遊戲刪掉是不可行的戒法，過不了幾天我一定會忍耐不住而又故態復萌。因此，我要找一個性質有點類似但不會沉迷的替代品。想來想去，最後決定來學高一時資訊課好像有教過的C++。當時我打的算盤是，從看手機變成看電腦應該也不會很難適應，而且我學個幾天應該就會覺得無聊而放棄了，到那個時候，電動的戒斷症狀應該會輕很多。
那個時候我問同學們要看什麼自學，我同學就推薦了[從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/)，我就開始把原本打電動的時間拿來看這份講義。
## 從零到十之旅
一開始的幾個章節稱不上是特別有趣，但也不會枯燥到難以下嚥，因此我就姑且看著學著，練習題也順順的寫著。然而，當我寫到 **0-8迴圈** 練習題中 [TOJ 120 Counting Stars](https://toj.tfcis.org/oj/pro/120/) 時，我想破頭也想不出來有什麼辦法能夠避免**TLE**。看了題解後，我被強烈的震撼到了。解答中使用的||前綴和||實在是無比精妙，將耗時的工作經過聰明的轉換有效率地完成。那一刻，我對coding產生了濃厚的興趣，想獲得更多這方面的知識，成為能運用許多巧妙工具的人。
大概花了一個半月，我將從零到一的講義看完了。當中有些練習題難度實在很高(STL篇章中:star::star::star:以上的題目)，甚至看了題解也還是不太會，最後就暫時跳過。這時，我開始認真考慮是不是要繼續學下去，考個APCS檢定，甚至是準備難度更高的比賽。
從零到一的目錄有推薦AP325作為接下來的學習內容，因此我就接著讀。從這時候開始，我分一半讀教材的時間在zerojudge上刷APCS的考古題。雖然常常會遇到寫不出來的題目，不過我認為那段自己什麼都還沒學但還是盡量想題目的時間中，我的思考能力進度很多，為學習AP325無形中提供了不少幫助。其中，我最有印象的是[血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967)，一道古老的APCS實作題p4考古，同時也是樹論中一個重要的例題。我當初刷到這題時，甚至不知道圖或樹這些概念，不過最後在畫一堆例子觀察後唬爛出||兩次dfs||的作法，並且實作完存圖與dfs等功能，終於成功拿到**AC**，開心了好幾天。順帶一提，我是在準備開始讀AP325的時候才終於下載了codeblocks，與之前一直使用的online GDB告別。
AP325是由吳邦一教授寫的，內容非常詳細，讀起來不太有看不懂的問題，其中的題目也幾乎都有辦法完成。花了一個多月，我將AP325讀完了，也練習到許多APCS考古題，我開始往下一個階段前進。
## CSES, Atcoder, and Codeforces
由於看到很多人推薦，我開始寫[CSES](https://cses.fi/problemset/)上的題目。由於我自己感覺在看完AP325後對DP還是不太熟，因此我從Dynamic Programming開始寫。寫到差不多後，我又把Introductory Problems和Sorting and Searching補掉一些。CSES上的題目幾乎都是經典題，對於新手來說CP值很高，不會被很多奇怪的題目打亂學習進度。
另一方面，我開始接觸線上賽。目前線上賽最有名的平台應該是Codeforces與Atcoder，兩者都會幾乎每週舉辦比賽。不過，Codeforces是俄羅斯平台，由於時區關係，比賽大多是在台灣時間晚上十點以後開始。我因為自己的作息較難配合，大多是參加日本平台Atcoder的比賽。BTW，我在這兩個平台上的handle都是**dnnnda**。
在每個禮拜參加Atcoder比賽的期間，我的實作速度開始顯著變快，最後去寫APCS考古題時都能提早大約半小時寫完，不過有沒有滿分又是另外一回事了。
就這樣，時間默默地來到六月中，我人生中第一場APCS檢定到來。
## 第一次考APCS
這次的APCS是在6月中，離我開始學寫程式已經有三個半月了。當時，我自認練習得相當充分，想要一舉拿下實作五級分，甚至還跟同學打賭，如果拿到實作五級就要來寫心得文紀錄。
考試分上下午，上午考觀念，下午考實作。考前，我有去官網上下載觀念題的參考試題，寫完後覺得觀念題要一起拿五級應該也有機會。不過，這樣的想法在第一節觀念題開考後就消失殆盡。之前有看過很多我覺得很厲害的人考APCS成績都是觀念4實作5，那時候我還覺得很疑惑，但在我看到觀念題的題目後才明白為什麼會這樣。
觀念題的題目比之前寫的參考試題更難，也更機車。不同於自己寫程式，觀念題需要看懂別人的coding邏輯，才有辦法快速知道一段程式執行後的結果。如果沒辦法由程式碼中的變數名稱等提示看出題目中程式的意義，考生就得化作機器，逐行執行程式碼，才有辦法得出正確答案。
最討厭的是，有些程式並沒有特定目的，單純就是要考倒考生，甚至很多題目都有兩個以上函式互相呼叫的遞迴，讓直接模擬程式執行窒礙難行。除此之外，很多題目中都會有故意寫得很醜甚至是寫錯的寫法，例如：
```c++
//正常人的寫法
swap(a,b);
//考試中會見識到的寫法
void swap(int& a, int& b){
int c=a;
int d=b;
a=a*b;
b=b*a;
a=a/c;
b=b/d;
b=b/d;
return;
}
//考試中會有的錯誤寫法
void swap(int a, int b){
int c=a;
a=b;
b=c;
return;
}
```
連swap(a,b)這樣基本的操作都可以玩出這麼多花樣，各位讀者應該不難想像以各種被亂寫的基本操作組合而成的題目，惡意有多明顯。總而言之，當我親自進入到考場後，就知道為什麼許多學校的APCS組都不會對將觀念題成績篩選，而只要求基本門檻了。
在結束早上兩節莫名其妙的觀念題考試後，來到午餐時間。由於我和我同學考完後都會討論題目，往餐廳移動的速度較慢，我們來到餐廳區時早就沒位置了。我們選定了一間看起來排隊的隊伍比較短的餐廳，在外面焦急地等了一段時間後，總算是成功拿到吃的，並且成功在下午時做題開考前解決掉。
時間到，我們進入考場，實作題測驗開始。前幾分鐘，我刻意放慢速度，仔細看清楚題目之前寫的作答說明，希望保持冷靜。這時候，我發現一件預期之外的事情：題本上要求考生將交出去的C++檔案以P1.cpp~P4.cpp命名。我在家練習時寫不同的題目都會共用一個檔案，因此不會遇到檔名問題，而意外就此展開。
我的[P1](https://zerojudge.tw/ShowProblem?problemid=o076)和[P2](https://zerojudge.tw/ShowProblem?problemid=o077)都是新開一個檔案寫，寫完就儲存、上傳，大概共花了30分鐘。接著，我在寫[P3](https://zerojudge.tw/ShowProblem?problemid=o078)的時候，使用了substr這個函式來拿取S的各個子字串，搭配set來完成問題。這時，時間還剩下90分鐘，我感覺一切順利，應該可以穩穩拿到5分，打開了[P4](https://zerojudge.tw/ShowProblem?problemid=o079)的題本。在看到題目的當下我有點呆住，沒什麼方向，思考過程中有想過是不是Greedy, DP或其他東西，最後在想了20分鐘左右想到了一個Sliding Windows的解並開始在P3.cpp中實作。
實作過程算順利，在本地跑範測也都沒問題，準備存檔時，我發現我寫P4的時候忘記開新檔案了，我直接把P3.cpp裡面的code刪掉然後寫在那裡面。因此，我想要另存新檔成P4.cpp。然而，這時候我另存新檔不知道遇上什麼問題，反正就是在講說我不能把這個檔案存成P4.cpp。
由於我覺得codeblocks不能一次開兩個檔案，我就把P4的code複製下來，把檔案關掉，準備把code貼在新開的檔案中。結果，我要貼上時發現`ctrl`+`v`按了一直沒反應，試了幾次後，我意識到我剛剛可能沒有複製成功。但是，我剛剛並沒有將P4的code存下來，因為我覺得我有把它複製到剪貼簿了所以不需要。也就是說，我的一頓操作讓我丟失了一份寫好的code。我看向時間，還剩下50多分鐘。我快速重整了一下心情，開始在新開的檔案中重現我剛剛寫的P4 code。
寫著寫著，我發現我不小心切到半形全形了。悲劇的是，我自己練習時從來沒有不小心按到過`shift`+`空白`，因此根本不知道要怎麼切換回去。我舉手請監考人員過來，並且說明狀況。他看了看，請另外一位監考人員去隔壁教室帶某個人過來幫忙。我焦急地等著，終於一個看起來蠻專業的人出現了。我再說了一次我的問題，然而他似乎也不知道怎麼辦，只在我的筆電上嘗試各種按鍵組合。大概兩分鐘以後吧，他賽到了。我的電腦終於可以正常打出半形英文。我趕緊把握時間，以我最快的速度寫code。
P4的code寫完第二次了，不過這次範測怎麼樣都跑不過。由於電腦並沒有提供在平常可以輸入input的地方貼上的功能，因此每次我修改一個地方，看有沒有成功時，我都要手動輸入範測。禍不單行，在某次輸入範測時，我又手賤按到東西。這次是按到`insert`，切換成了[覆蓋模式](https://zh.wikipedia.org/zh-tw/%E6%8F%92%E5%85%A5%E9%94%AE)。我又舉手請到那位幫我解除全形的工作人員，然而，這次他在一陣亂按以後表示他也不知道怎麼辦，我就只能在這樣的模式中修改程式碼。如果不是在debug時戳到這個東西，情況或許還不會那麼糟。
又過了一陣子，我找到P4的bug了，在修好以後順利通過範測並上傳成功。這時，我再次看向之前寫的code，做最後的double check。當我看到P3的substr函式時，我突然想到之前有看過一個說法是substr的時間複雜度是 $O(原字串長)$ 而非 $O(取的字串長)$ ，因此我的作法會拿到**TLE**。那時，我又想到字串可能會將很多本來是 $O(1)$ 的操作變成 $O(length)$，我就開始懷疑我把所有東西丟到set這個操作的時間複雜度會不會是 $O(LK^Llog(LK^L))$。算一算如果真的是這樣的話就相當於是n開到4.8e6的 $O(nlogn)$，帶的log還是set的log。我那時候不知道師大的judge到底能不能在一秒內跑過這樣常數偏大的東西，因此我決定自己刻非10進位的整數系統，將字串轉成數字後再丟入set中，讓整體複雜度降到 $O(LK^L+K^Llog(K^L))$。
最後的時間中，我把舊的P3.cpp刪掉、新開了一個P3.cpp，火力全開開始寫code。這次寫的過程也還算順利，範測都一次就過，我把code存檔、上傳到系統上後，看到在時間剩下2秒的時候系統顯示上傳成功，我也鬆了一大口氣。
出來後，我開始與同學討論，努力回想自己的code有沒有地方燒雞。突然，我想到最後p3我在寫字串轉整數時，為了方便把進制固定為11進制，而且我還是1-based的位數算法，因此int會overflow。可是我在場內並沒有注意到這個問題。總而言之，我的P3吃爆overflow造成的**WA**。
最後，這場APCS就以4+4級分(72+320)告終。~~在此建議大家考APCS的時候#define int long long~~。
## 暑假，大家都在讀學測
當初入坑時，我本來打算看能不能一次拿到APCS實作5級，接下來就專心準備學測，不過被深深吸引的我直接當作沒這回事，開始思考讀學測與繼續學程式並行的可能性。
二升三的暑假是準備學測的一段重要的時間，我不可能像以前一樣完全不管課業，每天只寫程式。六月底，我跟自己立下了一個約定：我要在七月把物理、化學、生物的複習講義寫完，把數學進度推到第一次模考範圍，並且同時認真讀英文補習班的東西。如果我七月的進度有達標，我的八月就要把時間分一半給coding(剩下一半讀地科)。
就這樣，為了能在八月時壓力比較小，我七月每天都到學校全天自習、爆刷複習講義。早上九點左右就到學校，自習到中午就和Alex, Max, 和 Arthur三個大捲王去買午餐。晚上的時候有時候會有人先走，但是我都會留到九點。那時候各科講義加起來每天都會寫大概7、80頁，雖然蠻累的但有設定一個目標就會很有動力。
最後，我七月的目標達成，八月的時候就開始繼續寫CSES，並且在TIOJ上開始寫校內能力賽初選考古題，為開學後的能力賽做準備。我學了線段樹和BIT，去寫了CSES的Range Queries，不過寫到Salary Queries和Prefix Sum Queries的時候發現我兩題都寫不出來，就先把Range Quries放到一邊，先去寫Graph Algorithms和Tree Algorithms。
Graph的題目我寫到一半覺得寫不下去，就跑去寫Tree了。Tree其實有很多都是dp，前一半的題目難度不大，寫完以後我戳了一些解，學會HLD和樹上啟發式後又做了剩下的一半，目前剩下兩題重剖還沒做。~~我好像應該先去學重剖而不是寫blog。~~
開學前，我感覺有很多東西要學，但沒辦法全部在校內能力賽前學完，因此我就去問pacybwoah要先學什麼，當時他這樣跟我說：//待補
所以我就去繼續寫Range Quries，想說要寫到懶標的地方。最後只留下Increasing Array Queries, Polynomial Queries和Range Queries and Copies沒有做出來。
## 校內能力競賽
:::warning
:warning: :warning: :warning:
警告：前方將有113建中資訊能力賽初賽+複賽暴雷
:warning: :warning: :warning:
:::
分為初賽和複賽，題目是由已經可以外加進北市賽的pacybwoah和owoovo準備，我們學校總共可以選出11+2個人去打北市賽。
[初賽](https://tioj.ck.tp.edu.tw/contests/100)開始20分鐘後，我把AB拿走，開始看後面的題目。我先戳了CD，看了看覺得C拿走25分就差不多了，D感覺有機會拿49。我先寫比較簡單的25分C，順利拿到後開始想49分D。49分D的1D/1D寫完以後出了一點bug，一直找不到。大概寫了一個小時我出去上了個廁所，回來以後bug就神奇的被找到了。看了看計分板，我要進複賽應該很穩，就跑去看了E。雖然E的題目看起來很複雜，但有56分的subtask附帶了$a_i=b_i$ 這個很強的條件。有這個條件後這題就變成簡單的Dijkstra，最後我在原訂比賽結束時間前15分鐘做完，順利拿到56分。
初賽的線是200多分，我順利以第五名的成績進入複賽。
初賽結束後，我開始寫複賽考古，發現總共五題的比賽我基本上拿不到任何**AC**。不過後來我知道複賽的線其實大概都是100多分，也就是說如果子題有好好撈，就算拿不到**AC**也會過。這段期間，第一階段培訓展開，課我(應該)都有好好上，有一次owoovo還教會我之前一直寫不過的[Elevator Rides](https://cses.fi/problemset/task/1653)。
複賽前，我感覺自己應該穩了。在寫考古題的時候幾乎每年都有在線上，初賽也喇分喇到第五名。複賽前一天，我去考了高二時很想進但沒進的數學能力賽校內培訓最終選拔，考出來跟同學對一對分數我就知道我數學校隊應該會有，整個人開始膨脹。晚自習時，還跟cactus分享我寫考古題的時候發展出的做題策略：
> 一開始先把所有題目看一遍，規劃好順序後再開始寫。看題目的時候，每題至少要停留五分鐘，因為我們常常看到很複雜的題敘就想跳過而沒注意到一些很好拿的分數。五分鐘的停留期間可以逼自己耐著性子理解題目並做出初步思考，接下來在規劃做題順序的時候會比較有方向。雖然開場就噴掉快半小時看題目，不過我覺得這樣花時間是值得的，因為這樣不太容易漏掉該蹭沒蹭到的分。
[複賽](https://tioj.ck.tp.edu.tw/contests/102)當天，我不知道哪來的想法，決定今天開場看題時間縮短到3分鐘以留更多時間給實作。各花3分鐘看完AB以後，我覺得我想到B滿分解了，就直接開始實作B而沒有去看C。那時候我寫線段樹的動作不算快，但我心裡想我做出這100分就穩了，因此整個人很chill。寫完跑範測以後，發現答案算錯了。我一步一步跟著算，才發現原來我一開始的想法是錯的！我整個人開始超級慌張，因為這時候已經過了快一個小時，而我這段時間內我還有3題沒看也沒有拿到任何分數。在勉強寫掉B的13分後，我開始繼續看題。
我開C出來看，看完只想到 $O(NM^4)$ 的dp和其他小子題。我開小算盤覺得$70^5$有點太大應該不會過，所以就先丟著。DE都是看完後幾乎沒什麼想就跳過了。我那時覺得，目前幾乎還沒拿到分，也沒什麼子題會寫，如果A沒想辦法拿滿可能很難進，於是目標訂成做出A的100分。
回去看了幾眼A，覺得應該怎麼樣都會用到隨機。可是，我那時候完全不會隨機的語法，只隱約記得time(0)好像可以吐出一個隨機數，因此我開始絞盡腦汁想要怎麼實作隨機的功能，後來，我用快速冪mod一個質數勉強算是實現了隨機，但是時間也逐漸流逝。
我發現我的目標是要找到0，在那之後感覺就很簡單了。後來，我想出一個很詭異的方法，有機會可以找到0，也想到可以問(a,a,b)來得知a和b的大小關係。不過我做法爛掉，不是一直把兩個數抓出來，然後把比較大的數字從0的候選名單中剔除，而是讓目前所有的0的候選位置跟某個random出來的基準比大小，如果比基準大就刪掉。但是，因為我的作法很爛、隨機數很爛，加上運氣不是特別好，我一直拿到**WA**20分，也就是一直沒蹭到後面大子題的分數。不過我太急、太緊張，沒有好好思考，發現其實有更簡單也更穩定的方法。接下來的一個小時，我就陷在debug pA的死胡同中。期間我有去撈pE的7分，然後吃爆WA就又跑回來A。
最後時間到了以後我只有61分，很明顯在線下:sob:。一個有好好撈分的例子是cactus，壓線進入校隊。說起來也是蠻可惜的，cactus這個要讀醫科的人主力拚的生物校隊沒進，意外進了資訊校隊；我努力想進的資訊校隊沒進，去考好玩的數學校隊反而進了$\dots\dots$
:::info
### 賽後檢討
這次有幾個燒雞點，照發生的時間列出如下：
- 亂膨脹
- 做跟原定策略不一樣的時間分配
- 想完B以後沒先對範測而直接實作，導致浪費過多時間
- 由於時間浪費太多，策略又跟平常不同，整個人開始很慌張，接下來整場比賽直接降智
- C沒想到$70^5$有機會過
- D沒想到Dijkstra可以這樣用、對二分搜不敏感
- E沒好好看題目和子題，miss掉7+26分很好拿的分
- A大耍笨
我那時候的能力就有機會拿到但沒拿到的分數：
A大概40
C 27分的$70^5$
D 21分二分搜 (0~21分Dijkstra)
E 33分簡單分
然後B有27分竟然剛好是我之前寫CSES Range Queries跳過的Increasing Array Queries:sob:
從這個慘劇中，我知道了以後最好不要賽中亂改之前想好的策略、相信不會被卡常。
:::
## 複賽後~~頹廢~~回復期
複賽死的這麼難看，我心裡當然不太高興，跑去看之前一直沒看的莉可麗絲回復能量(雖然後半的劇情其實get不太到)。遇到不愉快的事情時，似乎可以透過填充喜歡的東西或正能量的東西來暫時緩解情緒，但總是會有需要自己面對、治癒的部分。不過那個時候，我把這些暫時往後搬，畢竟莫名其妙進了數學校隊，當然開始準備數學北市賽，也趁這個機會沉澱一下。
北市賽結束，我拿了三等獎，對我來說很不錯。我自認有賽前盡全力準備比賽、賽中努力蹭分，不過如果去北市賽只拿個佳作甚至沒有獎感覺看起來很像只是來占名額的；如果我拿了二等獎，後面還有全國賽，而我不知道自己能不能在學測這個主線外，同時負荷數學和資訊兩個支線。
從我開始學C++以後，很多人都說我進步很快，而我自己也這麼認為。我覺得，我擁有不錯的資質，付出很多時間、心力在學習程式上，還身處一個有豐沛學習資源的環境。就算我起步比別人晚，應該也能打出不錯的成績。但是，我去考APCS沒拿到五級、比校內賽又被刷掉，讓我開始懷疑自己是不是不夠努力，有時候想這些的時候又會開始想自己是不是也沒有到那麼喜歡coding。
在我糾結這些時，接住我的是之前打日麻時鍛鍊出的心態。日麻是一個玩家就算擁有強大技術，也可能在短期內被運氣擊倒的遊戲。日麻圈中流傳著一句話：100個半莊都算是短期波動。就算自己不斷碰壁、選擇的策略或打法被結果否定，只要那是對的，我們都應該要堅持下去，如此才能在長期取得更好的結果。我跳出我的第一人稱視角，發現我的處境可能就像是一個剛入坑麻雀就連吃兩把四的新手玩家。如果我身邊有這樣的人，我一定會跟他解釋那是短期波動，並請他堅持下去。現在，我就是那個剛入坑就連吃兩把四的人，只要我有在失敗中找出問題，持續喜歡著這項活動並堅持下去，短期的結果就不那麼值得在意。雖然這其中可能有許多槽點，但我的感性接受了這樣子的說法。
我重新站了起來。
## 第二次考APCS
這次考試前，我還是覺得這次我可以五級。這次沒什麼新奇的點，除了實作的P3把我嗆翻。我賽中想不到複雜度很好的實作方式，因此我寫了一個感覺常數有點危險的方法。因為不想被卡常，我在裡面加了幾個常數優化，但最後跑他的範測都吃爆**WA**。
明明在本地跑的時候範測都有過，為什麼傳上去就**WA**?我專注思考這個問題，一次又一次測試那些可能在不同環境會有不同行為的指令，但沒有找到。結束後，我同學告訴我這次題本中的範測跟他幫我跑的範測是不一樣的，而且這個資訊有寫在注意事項中。因為已經不是第一次來考，所以我就沒有好好看注意事項，沒想到兩次的內容竟然不一樣，而且還是差在一個這麼關鍵的地方。看來，我是有其他地方寫爛，但我沒找到，想當然耳，這次實作又沒拿到五級。
## 啊啊啊要學測了啊啊啊
學測剩大概三個月，壓力漸漸變大，我雖然感覺自己還沒做足準備，但卻不願意放棄coding這個斜槓。我不像Arthur或Brian他們一樣，可以把自己逼得很緊來讀書，我需要可以轉換心情的活動。對以前的我來說，是電動；但對現在的我來說，是寫code。
讀書讀累了就去kenkoooo上戳一題1600左右的來想，是我、cactus和Steven一起享受的活動。
## 第三次考APCS
這場APCS跟上一場時間間隔不大，因此幾乎是上一場公布成績後沒多久就開放本場報名了。之前考APCS我都是準時早上九點上去搶考場，不過這次是Andrew當天中午提醒我我才知道要報名，那時台北只受下銘傳大學(要爬一點山)的考場了，不過我和Steven還是決定去考。
這是我申請入學前最後一次APCS，我抱著一定要考到實作五級分的決心參加(：啊以前不是也這樣說？)總之我這次多學了random相關的東西，讓我可以在場內自己生測資對拍，希望可以把最後多出來的時間兌換成分數期望值。
這場的觀念題難度有明顯下降，沒那麼多噁心的東西，看起來終於像觀念題該有的樣子了。中午，我和Steven下山找東西吃，結果最後也是吃捷運站的麵包店和便利商店，早知道應該多帶一點肉乾之類的東西。
實作題一二題還是不難，大概花了十分鐘寫掉。看[第三題](https://zerojudge.tw/ShowProblem?problemid=q183)的時候花了一點時間才理解題目在講什麼，理解以後也還沒什麼想法，想了一陣子以後就先去寫第四題。第四題不難，寫掉以後再回來第三題時，我右上角的倒數時間還有100多分鐘。在有這麼多時間的情況下只要寫出一題，我瞬間感覺放鬆不少。
由於真的沒什麼想法，我就先猜複雜度。由於 $n\le25$，我就先猜了比較有可能是 $O(2^n)$、$O(n\cdot2^n)$，備取複雜度是$O(n^4C)$ 之類的。一頓觀察後，我找到一個可能會讓複雜度裡面出現$2^n$的性質，我就開始繼續往這方面想。這時候我眼前的倒數時間已經從100多、90多，緩慢下降為80多了。
後來，我想出一個感覺蠻好時做的辦法。理論複雜度可能是$O((n+C)\cdot 2^n)$，不過我感覺要跑滿應該很難，就加了一些剪枝下去寫，我覺得寫的還算乾淨：
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int cnt[105], n, k;
vector<int> v, mn, mx;
void solve(int t){
if(v.size()==n){
vector<int> temp=v;
sort(temp.begin(),temp.end());
mn=min(mn,temp);
mx=max(mx,temp);
return;
}
while(cnt[t]==0) t--;
for(int T=0, u=t ; T<2 ; T++, u=k-t){
bool ok=1;
for(int i:v) if(--cnt[abs(i-u)]<0) ok=0;
if(ok){
v.push_back(u);
solve(t);
v.pop_back();
}
for(int i:v) cnt[abs(i-u)]++;
}
}
signed main(){
cin >> n;
if(n==1){
cout << "0\n0\n";
return 0;
}
vector<int> small(n,100), big(n,0);
mn=small, mx=big;
for(int i=1 ; i<n*(n-1)/2 ; i++){
int u; cin >> u;
cnt[u]++;
}
cin >> k;
v.push_back(0);
v.push_back(k);
solve(100);
for(int i=0 ; i<n ; i++) cout << mn[i] << (i==n-1 ? '\n' : ' ');
for(int i=0 ; i<n ; i++) cout << mx[i] << (i==n-1 ? '\n' : ' ');
return 0;
}
```
由於寫的時候有claim一些東西，再加上其他題我寫得很有自信，因此我投入了最後的50分鐘左右來做p3的對拍。
我在場內claim的其中一個東西是符合題目條件的最多就只有要輸出的那兩組數，因此我的對拍就這樣寫。另一方面，我沒有想到一個很好的方法來暴力跑遍一定範圍內的小測資，因此我就多random一些東西。
random很久後，我發現我的claim沒有被打敗，可能是因為這樣，我的剪枝非常有效，我幾乎不會吃**TLE**。到這時，我就鬆了一口氣，開始休息。
1/20，我收到了APCS成績單，我終於拿到實作五級分了。
註：我後來發現我的claim是錯的，只是random出來可以攻擊到的測資的機率太低，所以在場內才沒弄出來。而且就算符合條件的數不只兩組也不會太多，我的code還是能正確處理，因此有拿到滿分。
## 近況
3/2就是TOI初選了，幾乎剛好是我學競程一周年。利用這個寒假，我希望可以再多練題、vir比賽，努力進入1J選訓營。
老實說，剛開始學coding時，我覺得自己進度神速、超有天分，練一年以後應該可以變很強。但是，隨著學的東西變多、認識更多人，我才理解自己的渺小與無知。這個世界實在是太多神人，而且大家都老早就開始學coding，知道的東西比我多、想題比我快、實作又迅速，看著大家的背影真的感覺十分遙遠。
不過，**我還是會繼續下去**，在這個有趣的圈子中努力鑽研。
# Q&A
本文撰於2025年2月初，可能包含有時效性的資訊(尤其是聽說APCS考試制度要在2025年中大改版)，因此請對相關資訊保留懷疑。
## 競程是什麼?
競程(競技程式)是寫程式，或者coding中的一個特定領域，主要在用資料結構與演算法解決相關題目的要求。我認為競程對於想學程式的人來說是一個很好的切入點，因為它很有趣，不太需要記憶、背誦很多東西，大多著重在思考，卻可以拉近我們與程式之間的距離。
## APCS是什麼?
APCS是一個官方的免費程式能力檢定，~~雖然難度浮動很大而且是沒人喜歡的後測，但~~成績算是有公信力，是一個適合初學者參加的檢定。它分為觀念題與實作題兩部份，但個人認為觀念題很難準備也沒必要準備，因為其鑑別力實在不足~~也沒人在乎~~。
APCS實作題考的內容可以視為競程的基礎，可以作為競程入門者的目標之一。不過，它與大部分競程比賽最大的差別就是它是後測的，也就是考生無法即時知道自己送出的code是否有得到分數並做出修正。也因為這點，有些人在競程中已取得不錯的成果，APCS實作卻考好幾次才拿到5級分。
另外，許多大學資工系有開設APCS組，不過那並不代表只要考APCS就可以進入那些學校。對於台大等大學來說，APCS組是招收已經有一定程式能力的人，通常錄取者都還會外加TOI1J或科展等很強的經歷，因此不建議為了升學而勉強自己考APCS(沒興趣的話學什麼都很痛苦，也不容易學好)。
不過，對於非APCS組的考生來說，還是可以在一般組放上APCS檢定的成績來作為自己已經會基礎程式設計的加分經歷。
## 要怎麼自學
### 關於英文
如果對競程有些想法，那可能要有會看到英文題目或題解的心理準備。不過也不用太恐慌，因為其實這些英文都不會太難，沒過多久就會習慣了。甚至，如果真的很不適應，現在的AI工具很多，好好利用的話應該也可以逃避蠻久的，但若是要在線上賽使用，請自行注意相關規定。
### 關於語言
首先，如果你出於某些原因非常確定你的目標只有考APCS，那你可以選擇C, C++, Python, Java。不過，你如果有機會對更進一步的東西有興趣，我建議你學C++。
台灣有很多競程比賽限定只能使用C/C\++，而C有的功能C\++都有。此外，C\++的資源也比較多，我以下列舉的也都是for C\++的。
### 要在哪裡寫code
我覺得學習初期不一定要先研究這個，可以先使用online gdb之類的東西頂著，以後再決定要用什麼軟體。我自己是使用簡單的codeblocks，我身邊也有很多人是用VScode或Vim之類的東西，反正找一個自己喜歡、習慣的就好。
### 資源
[從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/)、[AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m)是兩份很好的入門教材。前者教你資料結構，後者教你基礎演算法。資結與演算法像是競程中的劍與劍術，幫助我們處理大量的題目。如果可以接受英文，可以直接看[CSES book](https://cses.fi/book/book.pdf)。
在那之後，如果想刷題可以去[CSES](https://cses.fi/problemset/list/)，想打比賽可以去[codeforces](https://codeforces.com/)或[atcoder](https://atcoder.jp/)，如果想繼續學東西可以翻[建中講義](https://tioj.ck.tp.edu.tw/articles/5)。
這些東西可以撐很久。當你跟這些都熟了以後，接下來要做什麼你就會自己知道了。
### 考APCS要看哪些
如果只有要三級分，那把從零開始的演算法競賽入門教學看完**0-8 迴圈**應該就夠了；如果想要五級分那可以把前兩份看完、寫掉CSES的sorting and searching, dynamic programming, graph algorithm裡面AC數>10000的題目，有時間再上zerojudge搜尋APCS把考古題刷一刷。這些都做完基本上就能五級了。當然，不用全部做也有機會有五級分，但就做越多越有機會。
### 關於zerojudge
可能有一些人會推薦/被推薦zerojudge這個網站，不過我個人不建議新手去上面刷題。zerojudge上的題目品質參差不齊，容易戳到沒營養或難度過低或過高的題目。不過有時候，有些講義開出題單有一部份的題目會在zerojudge上面，這種時候上去寫挑過的題就沒什麼關係。然而，送完解答以後可能會看到其他人在嘗試的題目，就會想要試試看，不過我覺得這通常沒什麼意義。如果想要有闖關、一題一題刷滿某個題庫的感覺，我強烈推薦[CSES](https://cses.fi/problemset/list/)。
## (某個年紀)才開始學會不會太晚?
不會。只要有興趣，什麼時候開始都不嫌晚。當然，越晚起步會越辛苦，畢竟時間會比別人少，可以參加的比賽也比別人少，但是，只要有興趣，就跟他拚了吧!
## 要怎麼平衡課業與程式
這是個好問題。我們一天如果睡八小時，醒來的時間就有十六小時。扣掉吃飯、洗澡之類的不可利用時間，至少還會剩下十二小時。如果這些時間都能夠被好好利用，那顧好課業和程式應該綽綽有餘。當然，現實中可能會遇到不能體諒你上課做其他課的老師、你想要進行一些休閒娛樂之類的，那這就要看個人的造化以及願意付出的心力了。
Sign in with Wallet
Connect another wallet