問題描述 給一棵 樹，每條邊都有權重，定義一條路徑的長度為該路徑上每條邊的權重和。 樹上的任何最長長度的簡單路徑都是此樹的直徑。 現在請你找到此樹上的任意一條直徑。 演算法 任選一點(令其為 $x$)出發，做一次 DFS 或 BFS 找到樹上離 $x$ 最遠的點 $y$，可證明點 $y$ 一定是某條直徑到其中一個端點，所以再從點 $y$ 出發做一次 DFS/BFS 找到離點 $y$ 最遠的點 $z$，那麼點 $y$ 和點 $z$ 形成的路徑就是直徑。

Bronze Problem 1. Hoof Paper Scissors Minus One 題目敘述 在遊戲 Hoof Paper Scissors 中，Bessie 與 Elsie 各自從 $N$ 個不同的手勢(蹄式)中選一個（編號為 $1$ 到 $N$），並根據一張規則表，不同手勢間比賽時會有兩種結果： 一方勝出、另一方失敗 平手 而在 Hoof Paper Scissors Minus One 中，兩隻牛各自同時出示兩個手勢（左蹄一個、右蹄一個）。各自手勢都被對方看見後，他們再從自己的兩個手勢中選一個作為正式比賽所出的手勢，最後依照規則表決定勝負。

賽前難易度猜測 D < C < A < E < B 實際每題 AC 人數 A：20 人 B：1 人 C：21 人 D：38 人 E：0 人

成績分布 :::success 以下題目的講解都已假設大家已擁有 AA 競程 Level 0 所介紹過的所有語法知識，而 Level 0 的教學內容可參考以下兩個網頁提到的課程大綱： AA 競程 Level 0 語法班 AA 競程 Level 0 競程入門班 ::: P1. 等紅綠燈

:::success 若有發現任何錯誤歡迎向 AA 競程臉書粉專回報 ::: 全國賽 承辦學校：國立政治大學(資訊學院) 比賽日期：12 月 6~7 日 正賽時間：12 月 7 日 09:00~14:00 比賽網站

成績分布 :::success 以下題目的講解都已假設大家已擁有 AA 競程 Level 0 所介紹過的所有語法知識，而 Level 0 的教學內容可參考以下兩個網頁提到的課程大綱： AA 競程 Level 0 語法班 AA 競程 Level 0 競程入門班 ::: P1. 裝飲料

全國賽官網 (連結已失效) 承辦學校：清華大學 各區決賽名次 區域 名次s 彰化、雲林、嘉義 22,31,34,39,45

成績分布 每題都有非常多種可獲得滿分的解法，但由於這是寫給 AA 競程的學員看的，所以會強調每題和課程內容的關聯性。其中， A, B 兩題只使用語法班教過的知識來寫 C 題使用競程入門班教過的知識來解 D 題則是使用 Level 1 教過的知識來解

1. 區間求和問題 此問題已經在這裡提過了 進階練習題：ABC 122 C - GeT AC 2. 差分序列 給定序列 $a$ (從 $1$ 開始編號)，我們定義序列 $a$ 的<font color="0x00ff00">前綴和序列</font> $S$ 的產生方式為 $s_i = \sum\limits_{j=1}^i a_j$ 類似的，我們定義 $a$ 的<font color="0xff00ff">差分序列</font> $d$ 產生方式為 $d_i = a_i - a_{i-1}$ (令 $a_0 = 0$) 兩個性質：一個序列的<font color="0x00ff00">前綴和序列</font>的<font color="0xff00ff">差分序列</font>就是自己。 一個序列的<font color="0xff00ff">差分序列</font>的<font color="0x00ff00">前綴和序列</font>也是自己。

1. 用陣列儲存資訊 我們可以使用陣列儲存和索引值有關的資訊，紀錄完後，就可以直接根據索引值以 O(1) 時間拿到我們要的資訊。 基礎題：計算數字個數 挑戰題：平均距離 2. 預處理 例題：連續和問題(CSES 1646 Static Range Sum Queries) 這種在回答所有詢問前先做一些處理的技巧被稱為「預處理」(preprocessing)。

賽前難易度猜測 A < B < C < D < E 實際每題 AC 人數 A：17 人 B：11 人 C：4 人 D：3 人 E：2 人

賽前難易度猜測 A < B < C < D < E 實際每題 AC 人數 A：64 人 B：33 人 C：30 人 D：14 人 E：3 人

賽前難易度猜測 A < E < D < C < B 實際每題 AC 人數 A：36 人 B：1 人 C：2 人 D：18 人 E：12 人

A. 加法問題 兩個 long long 相加範圍會超過 long long，直接相加輸出會 overflow。所以有些人的直覺是此題可能需要實作大數加法才能通過。 不過啊，GNU 編譯器有提供一個對競程來說非常作弊的資料型態 __in128 可以用，但是沒辦法直接用 cin、cout 輸入輸出，所以必須自己實作 __128 的輸出。 參考程式碼： #include<iostream> #include<string> using namespace std; int main() {

(2023 暑期的版本) <font color="#0f0">適合 AA 競程課程的人群</font> 對 TOI(台灣資訊奧林匹亞競賽)、USACO(美國計算機奧林匹克競賽)、CCC(加拿大計算機競賽)、Google Code Jam、Facebook Hacker Cup、Codeforces、Atcoder、ICPC 等演算法競賽有興趣且想要有系統的學習相關知識的人。 老師的戰績： Google Code Jam 2021 年 Round 3 Rank 26, 台灣第一。 Google Code Jam 2019 年 Round 3 Rank 25, 台灣唯一進入總決賽。 Facebook Hacker Cup 2016~2018 連續三年進入總決賽(每年取 25 名)。

網路免費學習資源 2014 資訊之芽算法班影片完全不知道時間複雜度的人請先看此影片 我們課程只做簡單複習及講解更深的內容 2021 資訊之芽投影片 計算演算法的時間複雜度的常見方法 一、數迴圈 請計算以下程式碼的時間複雜度

賽前難易度猜測 $E ≈ A < C < D < B$ 實際每題 AC 人數(包含同步賽) A：12 人 B：0 人 C：16 人 D：6 人 E：12 人

賽前難易度猜測 $A < C < B < E < D$ 雖然非出題者預期，但這場大概會被當作是個練習實作的比賽... 實際每題 AC 人數 A：16 人 B：8 人 C：8 人 D：2 人 E：2 人

賽前難易度猜測 E < B < C < A < D (其實老師覺得後三題難度差不多) 實際每題 AC 人數 A：10 人 B：14 人 C：6 人 D：6 人 E：9 人

賽前難易度猜測 C < B < D < A < E 實際每題 AC 人數 A：7 人 B：5 人 C：29 人 D：21 人 E：2 人