HackMD解題文件 APCS 202306 第一題 路徑偵測 (ZeroJudge k731) APCS 202306 第2題 特殊位置 (ZeroJudge k732) APCS 202306 第3題 磁軌移動序列 (ZeroJudge k733) APCS 202306 第4題 開啟寶盒 (ZeroJudge k734) APCS 2023.10實作題C++與Python題解 APCS 2024.01實作題題解 --- C++與Python APCS 2024.06實作題題解 --- C++與Python APCS 2024.10實作題題解 --- C++與Python APCS 2025.01實作題題解 --- C++與Python

在這份筆記中，我們說明APCS 2025年1月實作題考試的題目解說。這些題目是根據ZeroJudge上的版本，與真實考試的版本題意應該是一樣的，但題目敘述、測資與環境並不一定相同。 每一題的題解都包含題意分析、演算法、C/C++範例程式與Python範例程式。其中後兩個單元是獨立的，也就是必要的說明會在兩個單元重複出現，為了方便有些人只看其中一種語言。 第一題 等紅綠燈 (ZeroJudge q181) 題意分析 (題目連結)等紅綠燈 操場起跑線上有一個紅綠燈，綠燈為$a$秒，紅燈為$b$秒，依照綠燈紅燈的順序循環。 有$n$位小朋友，從操場的起跑線騎腳踏車在綠燈開始時一起起跑，每一位小朋友若騎到終點時為紅燈，需要等待紅燈結束變為綠燈才可以結束。 求出這$n$位小朋友共需要等待幾秒的紅燈秒數。

在這份筆記中，我們說明APCS 2024年10月實作題考試的題目解說。這些題目是根據ZeroJudge上的版本，與真實考試的版本題意應該是一樣的，但題目敘述、測資與環境並不一定相同。 每一題的題解都包含題意分析、演算法、C/C++範例程式與Python範例程式。其中後兩個單元是獨立的，也就是必要的說明會在兩個單元重複出現，為了方便有些人只看其中一種語言。 第一題 裝飲料 (ZeroJudge o711) 題意分析 (題目連結)1.裝飲料 有一個水杯，上下兩層是底面積都是正方形，但邊長不同。逐次加入若干體積的水，問哪一次水面高度增加的最多，假設水杯若滿，則高度不再增加。輸出水面高度最大一次的增幅。 演算法構思與程式流程

在這份筆記中，我們說明APCS 2024年6月實作題考試的題目解說。這些題目是根據ZeroJudge上的版本，與真實考試的版本題意應該是一樣的，但題目敘述、測資與環境並不一定相同。 每一題的題解都包含題意分析、演算法、C/C++範例程式與Python範例程式。其中後兩個單元是獨立的，也就是必要的說明會在兩個單元重複出現，為了方便有些人只看其中一種語言。 第一題 特技表演 (ZeroJudge o076) 題意分析 (題目連結)1.特技表演 在一個正整數序列$h$中，要找出最長連續遞減的區段，輸出其長度。 演算法構思與程式流程

(這個筆記大致取材於AP325第一章，但包含了一些關於遞迴更基礎與更詳盡的解說) 「遞迴是大事化小，要記得小事化無。」 「暴力或許可以解決一切，但是可能必須等到地球毀滅。」 「遞迴搜尋如同末日世界，心中有樹而程式(城市)中無樹。」 本章介紹遞迴函數的基本方法與運用，也介紹使用窮舉暴搜的方法。 基本觀念與用法 遞迴在數學上是函數直接或間接以自己定義自己，在程式上則是函數直接或間接呼叫自己。遞迴是一個非常重要的程式結構，在演算法上扮演重要的角色，許多的算法策略都是以遞迴為基礎出發的，例如分治與動態規劃。

「遞迴是大事化小，要記得小事化無。」 「暴力或許可以解決一切，但是可能必須等到地球毀滅。」 「遞迴搜尋如同末日世界，心中有樹而程式(城市)中無樹。」 本章介紹遞迴函數的基本方法與運用，也介紹使用窮舉暴搜的方法。 基本觀念與用法 遞迴在數學上是函數直接或間接以自己定義自己，在程式上則是函數直接或間接呼叫自己。遞迴是一個非常重要的程式結構，在演算法上扮演重要的角色，許多的算法策略都是以遞迴為基礎出發的，例如分治與動態規劃。 學習遞迴是一件重要的事，不過遞迴的思考方式與一般的不同，它不是直接的給予答案，而是間接的說明答案與答案的關係，不少程式的學習者對遞迴感到困難。以簡單的階乘為例，如果採直接的定義： 對正整數$n$，$fac(n)$定義為所有不大於$n$的正整數的乘積，也就是 $fac(n) = 1 \times 2 \times 3 \times \ldots \times n$。

「前綴和應該怎麼做呀？我煩到好像要死掉了！」 「錢墜河跟鑰匙掉了都一樣，撿起來就好了呀！」 (這是前綴和一個有趣的梗圖) 基本原理 Prefix前綴，也翻譯為字首，就是字串或序列從頭開始到某個位置的連續一段，相對於prefix，suffix就是後綴或字尾。顧名思義，前綴和就是數列前面一段的總和。若 $nums[;:n]$ 是一個整數序列，$prefix[i]$就是$sum(nums[; :i+1])$，即前$i$項的總和。下面是一個例子。 index 0

我們以LeetCode上的第一題來說明示範Python常用的搜尋技巧。 (題目連結) 1. Two Sum (Easy) 題目非常簡單：給一個整數陣列$nums$以及一個整數$target$，請找出兩個元素nums[i]與nums[j]，滿足$nums[i]+nums[j]=target$。 在這個題目中，它假設每一組測資都恰好有一組解，而且不可以找兩個相同的位置，也就是$i \neq j$。 這個題目雖然是Easy，但其實有不少可以拿來教學的東西。 最直接的方法是枚舉所有可能的$i$與$j$。 for i in range(len(nums)): for j in range(i+1,len(nums)):

程設資結迷惘，算法遞迴如夢，冷月豈可葬編程，柳絮靜待東風。 鄭愁予：「我打江南走過，那等在季節裏的容顏如蓮花的開落，東風不來，三月的柳絮不飛，你的心如小小寂寞的城，…」直到遇上了程式，……。 原C++版自序 寫書最難的是：不知道在跟誰說話。而教學最重要的是：見人說人話，見鬼說鬼話，意思是要用對方可以聽得懂的方式來解釋新的觀念與技術，演算法更是如此，因為演算法每個步驟要詳細到什麼程度沒有固定的表達方式。 這一份教材設定的讀者對象是已經對基礎的程式語法與架構有所了解，而教材的目的是透過解題的方式來介紹一些資料結構的使用與演算法的思考方式。以APCS實作題檢測的程度來說，教材的對象就是從三級分要進步到五級分的人，或者說是學會基礎程式後想要進入程式競賽的人。教材的主要內容是題目與解題的說明，每一個單元的前面也會有一些基礎知識的說明。雖然是解題為主的教材，但並不是去網路上蒐集題目與題解，而是判斷需要什麼才放什麼。因為也考慮對競賽程式有興趣的入門者，在選題目還是遭遇了一些取捨的困擾，後來有一些超過APCS範圍的題材也選了進來。除了一部份標註來源的題目之外，其餘的題目大部分都是常用來教學的題目與經典題，所以都沒有標註來源的問題，程式碼都是我自己寫的，也沒有標註來源的問題。 這份教材的一個好處是所有的題目都附了測資，讀者可以測試自己的程式。因為不想占用太大的空間，幾乎每個題目都只有放五筆測資，其實例題的測資產生程式都附在資料夾中，需要的人可以自己產生測資，部份題目我也放了效率較差的程式。理論上測資不可能防所有的假解，依我的判斷，在合理的狀況下這些測資都夠強了，當然，難免有意外發生的可能。對大部分的題目，時間限制都有很大的寬容度，效率好壞的算法差距應該都在幾十倍以上，但有少部份題目的差距沒這麼大，所以讀者必須自己判斷一下，尤其是要把題目放上裁判系統的人。

註：P開頭為例題，Q開頭為習題。例題習題中標示(@@)符號者題目稍難，標示(*)者可能超過APCS考試範圍，標示(APCS或其他出處者)表示該題出現於過去考試或比賽的類似題，如有標註subtask表示這一題的解法為當初考試的某一子題而非100分的解。 第0章 教材說明與預備知識 第1章 遞迴P-1-1. 合成函數(1) Q-1-2. 合成函數(2) (APCS201902) P-1-3. 棍子中點切割 Q-1-4. 支點切割 (APCS201802) (@@) Q-1-5. 二維黑白影像編碼 (APCS201810) P-1-6. 最接近的區間和 P-1-7. 子集合乘積

「樹上的問題大部分都可以用DP解決，一個變數不夠，就用兩個。」 「好想抖著拖鞋在樹上打扣，從上往下看，好多問題都變簡單了。」 這一章介紹樹(tree)，樹既然是一種圖，圖上的演算法例如BFS與DFS當然也都能用在樹上。但樹是特別稀疏的圖又有特殊的性質，所以很多問題在樹上有更好的解。另一方面，許多資料結構是使用樹的觀念建構出來的，本章探討的主要是輸入資料是一個樹的問題，而並非用樹做為資料結構的問題，這兩類問題並不相同。樹上的問題大部分都屬於貪心法則或是動態規劃，但需要搭配樹的結構來處理。 基本觀念與名詞 回顧一下圖的基本定義，一個圖寫作$G=(V,E)$，表示一個圖名字是$G$，由點的集合$V$與邊的集合$E$組成，其中$V$是點集合，也就是要研究的對象；而$E$是邊的集合，也就是誰與誰之間存在這種關係。樹(Tree)是一個連通而無環路的圖，通常指的是無向的簡單圖，也就是說若一棵樹$T=(V,E)$，則$m=n-1$，其中$n$與$m$是點數與邊數。 為了方便或需要，我們可以指定其中一點為根(root)，稱為有根樹(rooted tree)，一旦指定根之後，我們可以給圖上的邊訂定方向，每個邊的方向是由根往其他點，或者尤其它點往根的方向。通常把樹畫成一個家族圖，根在最上方，也就是說所有的邊都是一個上下兩點的關係，tree所代表的二元關係就被比喻為parent與child的關係。下圖是一個有根樹，其中0是根。除了根以外，每個點的上方恰有一點與其相連，這個點稱為他的parent，例如4與3的parent是1；而1與2的parent是0(根)。若a是b的parent，則稱b是a的孩子(child)。只要指出每一個點的parent就可以惟一決定一棵樹。以下介紹一些基本的知識與名詞。 

分治：「一刀均分左右，兩邊各自遞迴，返回合併之日，解答浮現之時。」 「架勢起得好，螳螂鬥勝老母雞。在分治的架構下，簡單的資料結構與算法往往也有好的複雜度。」 這一章介紹分治演算法(Divide-and-Conquer algorithm, DaC)，又稱分而治之演算法，也有人稱為各個擊破法。分治是一種非常重要的演算法思維模式與策略，有很多重要的演算法都是根據分治的思維模式，例如快速排序法、合併排序法、快速傅立葉轉換(FFT)、矩陣乘法、整數乘法以及在一些在計算幾何的知名演算法都是分治的策略。相較於它的重要性，分治出現在題目中的比例卻不是那麼高，主要原因有二：第一，很多分治算法的問題都有別的解法的版本，樹狀圖的分治也往往歸類到動態規劃；第二，一些重要的分治算法已經被納入在庫存函數中，例如排序，還有一些則因為太難而不適合出題。 即使如此，分治還是很重要必須學習的思維模式，當我們碰到一個不曾見過的問題，分治往往是第一個思考的重點，因為分治的架構讓我們很容易找到比暴力或天真做法要好的方法。 基本原理 從名稱divide-and-conquer就可以看出來，分治算法的精神就是將問題切割後再克服，事實上，分治的算法都可以分成三個主要步驟： 切割。將問題切割成若干個子問題，通常是均勻地切成兩個。

AP325-Python 自序 AP325-Python 第0章 教材說明與預備知識 AP325-Python 第1章 遞迴 AP325-Python 第2章 排序與二分搜 AP325-Python 第3章 佇列與堆疊 AP325-Python 第4章 貪心演算法與掃瞄線演算法 (I) AP325-Python 第4章 貪心演算法與掃瞄線演算法 (II) AP325-Python 第5章 分治演算法 AP325-Python 第6章 動態規劃 (I) AP325-Python 第6章 動態規劃 (II)

Chapter 8 (III) P-8-11. 公司派對 (NCPC) 有一個公司有$n$個成員，成員以1 ~ $n$編號，每個人都有一個領導，除了編號1是公司的總裁，他沒有領導。現在要辦一個公司派對，想要邀請一些人來參加，如果邀請了編號i的人來參加，就會有$r(i)$的歡樂指數，可是，這個公司的任何人都不想跟他的領導一起參加派對，請你幫忙計算要邀請那些人來參加，才可以讓參加者的歡樂指數的總和最大。 image 右圖是一個例子，每個圓圈代表一個人，圓圈內的數字是他的歡樂指數，每個人上方與他連線的就是他的領導，你可以看到，總裁的歡樂指數是1，也全公司最低的。我們可以看到此例中有兩個人的歡樂指數是14與11，可惜14是11的領導，所以不能同時邀請這兩人參加。這個例子的最大歡樂指數總和是66，扣除歡樂指數分別為1,3,3,4,14那5個人，其餘的人都參加。 Time limit: 2 秒

Chapter 8 (II) 例題與習題 在這一節中我們介紹一些典型的樹狀圖的題目，不外乎貪心法或遞迴，也有些是模擬或走訪。下一題曾經出現在P-3-1，當時是介紹由下而上的走訪方式，而且還沒介紹什麼是DP，在學過DP以及樹的DFS之後，這一題應該變得簡單很多了。 P-8-4. 樹的高度與根 (同P-3-1) (APCS201710) 有一個大家族有$N$個成員，編號1 ~ $N$，我們請每個成員寫下此家族中哪幾位是他的孩子。我們要計算每個人有幾代的子孫，這個值稱為他在這個族譜中的高度，也就是說，編號 $i$ 的人如果高度記做 $h(i)$，那麼 $h(i)$ 就表示在所有 $i$ 的子孫中，最遠的子孫與他隔了幾代。本題假設除了最高的一位祖先(稱為root)之外，其他成員的parent都在此家族中(且只有一個parent)。本題要計算所有成員高度的總和以及根的編號。 image

Chapter 7 (III) 補充教材(*) 在這一節中，我們挑選一些還算常用也不太困難的圖論演算法當作補充教材，包括：Dijkstra演算法、併查集(Union and Find)，以及最小生成樹(Minimum spanning tree)。這些內容研判超過APCS考試範圍，所以讀者可自行選擇是否略過。 Dijkstra演算法 我們前面介紹了無加權圖上面以BFS計算最短距離的方法，對於DAG我們也可以沿著拓樸順序來計算距離，但是應用問題中，更常見的是邊上有加權也可能有環路的圖。Dijkstra演算法是用在一個加權圖上計算一點到所有點的最短路徑的演算法，圖可以是有向的或無向的，但是邊上的權重必須是非負的。 假設輸入的圖是$G=(V,E,w)$與一個起點$s$，我們要計算$s$到$V$中每一點的一條最短路徑。演算法運作過程中，我們以$d[v]$紀錄目前已知$s$到$v$的最短距離，集合$Q$表示最短距離尚未確定的點，演算法如下：

「BFS、DFS、與Dijkstra演算法之間有何差異？」 「BFS像是小寶寶自己找父母，出生第一眼就到的就認做parent；DFS像是幫孩子找爹娘，最後結婚生下的才是你孩子的parent；Dijkstra則是長大後自己找乾爹乾媽，最有利的才是乾爹乾媽。」 「那麼，Prim與Dijkstra演算法的差異呢？」 「認乾爹乾媽的依據稍有不同。Prim只看乾爹乾媽對你有多好，Dijkstra則除了對你多好之外，還有他從祖先繼承了多少會留給你的財產。」 這一章介紹圖(graph)，圖是用來表達二元關係的一種方式，有很多重要的應用，也發展出很多特殊的演算法，這些演算法都是過去科學家研究發展出來的，也就是說，我們要了解它的話，需要靠學習與理解，很難只靠基本的演算法原則自己去想出來。 圖在競賽程式中也扮演了很重要的腳色，但基於高中資訊領域的範圍與APCS的考試範圍，這份教材只會包含一些圖的基本演算法。本章內容包含：圖的基本觀念與名詞、儲存圖的資料結構、廣度優先搜尋、深度優先搜尋、以及DAG與拓樸順序。 在本章最後我們則介紹了三個比較進階的技術，包括Dijkstra演算法、併查集、以及最小生成樹。至於在樹狀圖上做計算的相關問題則留在下一章。

Chapter 6 (III) 2D1D與其他 下一題也是學DP的經典練習題。 P-6-17. 切棍子 有一台切割棍子的機器，每次將一段棍子會送入此台機器時，我們可以選擇棍子上的切割位置，機器會將此棍子在指定位置切斷，而切割成本是該段棍子的長度。現在有一根長度L的棍子，上面標有 $n$ 個需要切割的位置座標，因為不同的切割順序會影響切割總成本，請計算出最小的切割總成本。 下圖是一個例子，切割點是$[3,5,1,4]$，如果依照$3\rightarrow 5 \rightarrow 1\rightarrow 4$的順序切割，第一次的長度是7，第二次切割時所需切割的棍子長度是$7-4=3$，第三次切割時，成本是$3-0=3$，第四次成本是$2$，總成本是$7+4+3+2=16$，這是本例最小的成本。 (註：本圖例取自LeetCode)

Chatper 6 (II) Alignment是生物序列(如DNA與蛋白質)分析的重要問題，輸入兩個字元序列，我們要將兩序列的字母依照原順序做一個對應，過程中可以將任一序列的某些位置加入空白，以輸入”CTTAACT”與”CGGATCAT”為例，以下是一個可能的alignment (以-表示空白)： CTTAAC-T CGGATCAT 以下也是一個alignment： C---TTAACT CGGATCA--T

「每一個DP背後都有一個dag，DP需要dag指引方向，如同視障者需要dog。」(Dynamic programming, Bottom-up) 「設計DP以尋找遞迴式開始，以避免遞迴來完成，除非，除非你準備小抄。」(Dynamic programming, Top-down memoization) 這一章介紹動態規劃(Dynamic Programming, DP)。DP名字中Programming的意思是指「以表格紀錄」，而非現在常用的「寫程式」，所以DP的意思是以變動的表格來求解的方法。 DP的應用很廣，變化很多，在學術界也發展的很早，在程式競賽也用的非常多，並且有很多困難而精妙的(優化)方法。這本教材只限於一些常用的典型的題型，此外樹與圖的DP將放在後續討論樹的專章中，而不在本章中。 基本原理 基本思維與步驟 DP與分治有個相同之處，都是將問題劃分成子問題，再由子問題的解合併成最後的解，其中子問題是指相同問題比較小的輸入資料。所以，設計DP的方法從找出遞迴式開始，設計DP的演算法通常包含下面幾個步驟：