Author: H.Y. Chen
-
24/05/2025
跟CSES沒關係的比賽心得文，4~5月自己去報名了很多比賽，今天比完北商九校聯盟的競賽，我的比賽月也告一段落了，所以香說來做個總結。 4/12 去比了大專盃的黑客松，原本自信滿滿，想說我前端好歹也學了那麼久(其實也才1年)總該派上用場了，所以超認真的用figma，還連一大堆動畫，結果…人家根本不care!!這是場比arduno的比賽!!!。。。雖然什麼都沒拿到，但解鎖成就: 5/3 去功利的復興比了高職的資安主題黑客松，原本以為我可是自己做了一個django失物招領的人!!結果人家比的是資安。。。一樣GG，但解鎖成就: 5/10 去至理比了codejudger的比賽但那個可以用錢買題目所以這裡先不說了 5/24 就是我們北商跟另外8校的9校聯盟程式競賽了，比的是我會的東西，題目沒辦法用錢買到。從報名後我就只告訴自己: 證明自己就行了。 這裡要先感謝一個人 – 李董，雖然我覺得他不會翻到這篇文章，但還是很感謝他，競程這種東西真的都是他教我的，能有今天的結果50%是他的功勞。 先說今天發生的事: 進階組一年比一年難，9/20拿了個進階組佳作，變成校內進階組排行第二(第一是李董，果然，名師出高徒阿!)，頒獎唱名時，司儀還特別說:其中，陳泓毓同學更是首次挑戰進階組就取得佳績。原本這已經夠爽了(雖然只有佳作還是有點小失落)，結果沒想到在進階組命題老師上去致詞時(aka 裁判長、研究所主任)竟然說:尤其是這個五專二甲的陳泓毓同學阿，才二年級就在\進階組拿到了不錯的成績是校內第二! 超爽天啊，後來我們班導還一直跟那個命題老師說我坐在哪我是誰，雖然我還是輸以前是國手的兩個學長(初階組1、2名)以及我大李董，但“全校第二”這個頭銜已經很爽了，哈哈哈哈。 時間推回比賽前 – 2天。 有個也很常教我寫程式的學長(以下簡稱緯子哥)勸我還是去初階組比較好(因為我報進階組)，說我去初階穩拿優選甚至可能前三，幹嘛要去進階組拿佳作? 但說真的，比賽不就是要比說自己的能耐到哪嗎，都已經確定穩拿了，那比賽的意義又在哪裡? 會一直往上挑戰，那才是我。不然我就待在音樂班舒適的小圈圈就好了沒事學什麼資管? 時間推回比賽前 – 3個禮拜~比賽前4天。 我禮拜二都會教我們班另外三個也有報名(初階組)的寫競程，班導問我為什麼還願意花自己的時間去把其他同學拉上來?(有兩個拿到佳作)有幾個原因，1是不忍心看他們被電太慘，2是想練習”教程式”這件事(畢竟當個好老師真的很難)，3就比較現實，我單純想讓他們知道初階組對我來說很簡單w(對就是在炫耀) 其實最主要的原因是2，畢竟當個”會教的老師”這件事是需要時間去堆積經驗的，(訓練系統化的整理必口述表達)這種邏輯的東西是最難教的，我如果30歲才開始練習，那我不就要等到到五六十歲才能變好老師?現在開始練習的好處是1 沒收人家錢，如果教完還沒得獎，罪惡感比較不會那麼大w ，2是就算講錯，人家也只會覺得你是學生，這樣已經很好了 總結就是“我有很多犯錯的空間，那何不現在就開始練習當個指揮家?” 時間推回比賽前 – 報名開始前 先說個題外話，我一直都覺得，五專這種學制，重要的就是校外或競賽的成績，而不是學校內的班排 – 考試都考背的，會背就好根本不用動腦。。。 班排一能證明什麼?你很會背東西?能幹嘛? 所以我一直覺得我們班的很多人很可憐 1.是整天漫無目的問吃等死型 2.是把這裡當高中過的人 – 什麼都學了但什麼都不會 那時候要報高中職黑客松的時候，我都已經說我會react,django,spl等，還是沒人要跟我一起報名，那個時候我基本上就知道我們班大家的程度了… 為什麼我一直管人家?不好意思，我之後專題不太可能一人一組阿!! 所以真的很欣慰(? 這次競賽我們班有人願意堅持到最後一刻 真的是個不錯的經驗 這次拿佳作，還好不是優選，不然大家就會說明年要看你拿前三了w 謝謝主任讓我去商智中心，謝謝商智中心的所有人，react,django,python,java等等等，自學的路上，到處都是你們的身影。 一年而已，我從連windows怎麼用都不會的人，到現在做了一個失物招領系統，拿了佳作。背後真的太多要謝謝的人，不是拍馬屁，是真的很感謝，不然也不會有今天的我! 感謝 按認識時間排序(綽號) 君姐(html,react)，李董(python, django,…
-
Static Range Sum Queries
前綴和會使時間複雜度變： 建立前綴和：O(n) 回答每筆查詢：O(1) 所以總時間：O(n + q) 但是python I/O過慢會導致超時，所以可以在前面 import sysinput = sys.stdin.readline 加速input 前綴和可參考：https://hackmd.io/@HyC-1029/By-o9OAoyg
-
Counting Rooms
這種題目不是一般常見的樹狀圖或其他有節點的圖，而是自訂的迷宮圖，這種題目常見的解法就是用bfs,dfs去跑，另開一個visited來記錄走過的。 詳細：https://hackmd.io/@HyC-1029/rkwgn3OWeg Flood Fill 演算法 從目前的點向四周擴散，像洪水一樣因而得名。 遍歷整張地圖，每當你發現一個還沒走過的 ‘.’，就： 結果當m,n 都是1000時就會超時了，因為這遠遠超出了python遞迴的極限。 待
-
Sum of Two Values
想法 – 1 用hash map, 也就是python的dict來記錄下位置，並在每一個迴圈都比較現在 x-i的值有沒有在li裡，有的話就輸出dicta對應的位置。 但是這種寫法會跑太多迴圈，超時。（ 因為 li 是個 list，in 判斷會是 O(n) 的操作。整體會退化成 O(n²)！）即使改成if s in d 也還是會超時！！ 改Ｃ＋＋ 並且在同個迴圈中加入map，避免「重複的數字」只保留到最後一個出現的位置，也減少迴圈運行的時間
-
Restaurant Customers
題目說測資會到10**9，接近好幾GB了，所以本篇介紹兩種寫法，如果測資小的話可以考慮用第一種寫法。 想法 – 1 差分, 前綴是啥可以參考這篇 : https://hackmd.io/@HyC-1029/By-o9OAoyg 想法是:透過差分來標記區間[a:b]內有人，然後再用前綴和將正確人數還原出來。 // 小心如果測資>10**6的話就會爆炸 想法 – 2 因為CSES的測茲有一個20,000，兩個迴圈來回就直接超時了(記憶體也爆掉)， 所以改是看看用C++線性搜。 一樣跟差分的想法，只要有人我就+1來計算進場人數，不過最後是一直比對 max()。 假設現在有一個input是 (1, 4)(2, 5)(7, 8) 我們用pair(a,x)將這筆資料存到vector中，a表時間，x表進場人數，會變 vector= {{1, +1}, // 1點來一人{2, +1},{4, -1}, // 4點走一人{5, -1},{7, +1},{8, -1}} 接著再透過累加的方式線性搜
-
Concert Tickets
用python容易超時，不超時的話要用外部額外排序list套件，但要用到外部套件就不是個好選擇了，所以這裡提供用python表示想法，會用C++來實作 想法 仔細想想就會發現這題比較沒辦法用雙指針(因為涉及刪除)。 所以這裡的想法是 ” 將顧客的預算插入到票價list中，取左邊那個 “ 這樣就能取到<=票價的最優價格了 bisect.bisect_right(s,t) 會回傳” c要插入s裡的最佳index “ 所以透過套件快速二分搜來達到快速找到該值右邊index C++ 透過multiset的upper_bound 來達到同樣效果，且multiset可以依值保持有序
-
Ferris Wheel
看到題目就知道要用貪心，因為我們要一直找體重最接近x的人來湊， 除非>x，否則ans+=1。 除了貪心，還可以用雙指標–頭尾往中間，但是為什麼? 假設現在有一個小到大排序好list，因為一個車廂可以載最多2人，所以我們可以考慮把 “最重(right)跟最輕(left)” 放在同一車廂，盡可能的在 right-left <= x 的情況下接近x。