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

前言

第一次打北市賽,也是最後一次,雖然說好像進步空間還很大(好像還可以再多個 100 分,不過這樣也頂多三等獎 ww),從今年三月上資芽算法班第一次接觸演算法,不過我應該是高三開學才開始在練題目,然後校內賽完開始培訓才開始練比賽(個人感覺練題目跟練比賽好像不太一樣,通常練題目習慣應該就是要拿滿分解,但競賽是要快速得到你所能得到的最大分數,這也跟我沒少拿了差不多 100 分有關 QQ)。

pA 100/100

這題有點像約瑟夫但每個人有 \(K\) 條命,然後每次經過 \(N\) 個人,但好像師大伺服器比較快?時限 2 秒,我想說先用 linked list 試試看複雜度 \(O(NSK)\)(\(N<10000, S<500, k<6\)),然後就 AC 了!(好像有人 \(N^2 K\) 過了,師大測資 XD),賽後才知道好像用線段樹可以有 \(O(NK log N)\),寫法大概應該就是我之前寫的那題 APCS-2016-1029-3 定時 K 彈

pB 17/100

我 de 了一個半小時的 bug 結果只有 17 分🥲,大燒雞。
題目是說有兩類保健食品,各 n、m 個,然後接下來會說哪些不能一起用,問說能一起用的最大保健食品數,我一開始是把不能一起的連在一起做最大匹配,最後再輸出全部剪去最大匹配的數量,不知道哪裡有問題,只有第一子題對,後面都 WA,感覺應該是我少判了什麼(其實我在這題之前根本沒寫過最大匹配的題目 www),但因為可能剛好第一子題沒有戳到所以就過了🤔

pC 100/100

這應該是這次最水的,我有點忘了題目是什麼,但我好像是用有點用雙指針的方法,然後我用 map 存某個東西,最後複雜度是 \(O(N log N)\),這題好像 10 分鐘我就寫完了

pD 0/100

區間眾數裸題,不過我不會,我想說用線段樹撈子題(結果賽後別人講才知道用前綴和就能撈了🙃,資結中毒),然後我把邏輯判斷的 && 打成 ,,超級笨我花了 10 分鐘找 bug 結果找不到,就到此結束了...

pE 0/100 (沒看到)

pF 0/100 (沒看到)

總結

策略錯誤🫠,雖然好像常常總是有人講說要先看完所有題敘按順序寫,不過我總是想說我就按順序看,要是我有想法我就直接做一做,反正如果說我看完發現其他更簡單的,前面次簡單的題目我也一定能做出來,還能省下重複讀題的時間,結果就是大燒雞🐓,聽說第六題好像挺簡單的,真的好可惜。

另外這次題目真的有比較簡單,比賽前我們模的每場都還簡單,也很明顯出現了四個破台,然後我只有佳作🥲,不過已經還可以了啦。半年前資芽算法班接觸到演算法,兩個月前開始練題目,同時還有特選在忙,在⼀次次的練習中我了解到我在程式競賽上的天分,我漸漸能跟上早我⼀兩年開始的其他⼈,能⼀起討論題⽬,⽽最後在北市賽中得到佳作,只拿到兩題全對和⼀題⼦題分數,我知道我的實⼒應該還可以更⾼,⾄少在⼦題的部分還可以再拿到快⼀百分,我會繼續練習,也希望能在不久後的 NPSC 拿到好成績,總之,這次經驗真的是很值得紀念。

最後成績:
總分 217/600
rank 45