# AA 競程課程介紹 (2023 暑期的版本) --- ## <font color="#0f0">適合 AA 競程課程的人群</font> ---- 1. 對 [TOI](https://tpmso.org/toi/)(台灣資訊奧林匹亞競賽)、[USACO](http://www.usaco.org/)(美國計算機奧林匹克競賽)、[CCC](https://www.cemc.uwaterloo.ca/contests/ccc-cco.html)(加拿大計算機競賽)、[Google Code Jam](https://codingcompetitions.withgoogle.com/codejam)、[Facebook Hacker Cup](https://www.facebook.com/codingcompetitions/hacker-cup)、[Codeforces](https://codeforces.com/)、[Atcoder](https://atcoder.jp/)、[ICPC](https://icpc.global/) 等演算法競賽有興趣且想要有系統的學習相關知識的人。 ---- 老師的戰績： * Google Code Jam 2021 年 Round 3 Rank 26, 台灣第一。 * Google Code Jam 2019 年 Round 3 Rank 25, 台灣唯一進入總決賽。 * Facebook Hacker Cup 2016~2018 連續三年進入總決賽(每年取 25 名)。 * 詳細各大比賽戰績可參考： [Competitive Programming Hall of Fame](https://cphof.org/profile/topcoder:dreamoon) ---- 2. 對 Leetcode、Google Kick Start 等面試導向的算法題有興趣的人。 ---- * 老師的戰績： * 在 2013 年 Round A 第一次參加就拿了第一後覺得沒意思，到了隔年 2014 年 Round D 再次參加又是第一後，就對 Kick Start 失去興趣，沒再參加了。 * 數次在 Leetcode 比賽獲得第一名 * 目前穩定在 [Leetcode 排行榜](https://leetcode.com/contest/globalranking) 前 50 名 ---- 3. 想要在 APCS 程式檢定取得實作五級分的人。 ---- 老師的戰績： * 2021 年 1 月參加了一次 APCS 體驗看看，實作場 30 分鐘(整個考試共 150 分鐘)就寫完走人，拿了 400 分滿分。 ---- * 有人會質疑老師很強跟老師很會教是兩回事，但很強的老師才有辦法把所有知識做有系統的整理，也能夠回答學生各種難度的問題，不會遇到學到一定程度後，就得換老師這種事。 ---- * 我們經營第一年就有其他機構無法比擬的成績作為佐證 ---- <iframe src="https://www.facebook.com/plugins/post.php?href=https%3A%2F%2Fwww.facebook.com%2FAAdreamoon%2Fposts%2F399008741997244&show_text=true&width=500" width="500" height="756" style="border:none;overflow:hidden" scrolling="no" frameborder="0" allowfullscreen="true" allow="autoplay; clipboard-write; encrypted-media; picture-in-picture; web-share"></iframe> ---- <iframe src="https://www.facebook.com/plugins/post.php?href=https%3A%2F%2Fwww.facebook.com%2FAAdreamoon%2Fposts%2Fpfbid07mzZ9aeQ7Fzr2xvSgXHWAP8iUE5xe1h5xuV3HupTigsUBV1NgbhFc8Lfo1xSr1KSl&show_text=true&width=500" width="500" height="794" style="border:none;overflow:hidden" scrolling="no" frameborder="0" allowfullscreen="true" allow="autoplay; clipboard-write; encrypted-media; picture-in-picture; web-share"></iframe> ---- <iframe src="https://www.facebook.com/plugins/post.php?href=https%3A%2F%2Fwww.facebook.com%2FAAdreamoon%2Fposts%2Fpfbid02EUnB2cxoqEESMYDJnpP6s6E7ctyN5bHVk1Noiy9b1KiB7pBLqzrHzCTT1F9QkF7ol&show_text=true&width=500" width="500" height="642" style="border:none;overflow:hidden" scrolling="no" frameborder="0" allowfullscreen="true" allow="autoplay; clipboard-write; encrypted-media; picture-in-picture; web-share"></iframe> --- ## <font color="#0f0"> AA 競程課程總覽 </font> ---- ### 課程設計與學員目標對照圖  ---- ### 目標為 USACO * 想通過銅組(Bronze) 進到銀組(Silver) 須熟悉 Level 0 甚至是 Level 1 中比較淺的內容 * 想通過銀組(Silver) 進到金組(Gold) 須把 Level 1 了解透徹 * 想通過金組(Gold) 前進白金(Platinum) 至少要學習到 Level 3，甚至 Level 4 以上的內容都有可能出現在金組 ---- ### 課程與課時、練習時間關係圖  ---- ### 課程與台灣競賽對應獎項  --- # Level 0 課程介紹 ---- Level 0 分為「語法班」以及「競程入門班」 ---- ### 語法班 * 教 C++ * 就算學過其他程式語言，但沒接使用過 C++ 都得從此班開始學起 * 就算學過 C++，但用 C++ 解題經驗很少，也要從此班開始學起 ---- ### 競程入門班 * 介於語法以及資料結構演算法之間的銜接課程 * 課程目的有二： 1. 增加學員實作的能力 2. 增加學員的數學能力 --- # Level 1 課程介紹 ---- Level 1 的課程內容包含但不限於： * 時間複雜度 * 基礎數論 * 枚舉 * 遞迴 * 雙指標 * 貪心 * 二分搜 * STL 容器及其應用 * DFS & BFS * DSU * 分治 ---- * Level 1 以上課程的教學方式：用老師自己設計或精挑細選的題目來帶入基本觀念 * 課程教學目標： 1. 教大家看到題目時，怎麼把題目和學過的資料結構與演算法連結 2. 提醒大家所教的演算法有哪些容易出錯的地方 ---- * 老師把幾萬小時的解題經驗抓出重點作出總結，把演算法解題的基本精神放在 Level 1 教給大家，是所有課程中最精彩、CP 值最高的一堂課 ---- * 若你已經熟悉 Level 1 的知識，那麼你應該要能輕鬆解出 [LINK START!](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/U) 這道題唷 ---- * [LINK START!](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/U) 是 2023 年黃老師出在 TOI 模擬賽的題目，是 Level 1 中「枚舉」的概念的應用題，但是仍有進到 TOI 2 階的選手沒能解出這題 * Level 1 裡會教大家許多在此題難度以上的題 --- # Level 2 課程介紹 ---- Level 2 的課程內容包含但不限於： * 動態規劃 * 基礎排列組合 * 倍增 * 樹狀陣列 * 矩陣及其應用 * 基礎線段樹 * 最短路 * Level 1 課程內容如二分搜、DSU 的進階應用 ---- * 上課方式和 Level 1 一樣 * 動態規劃佔 Level 2 的一半內容 * 若只要是想學動態規劃，可只報名 Level 2 的上半期 * 若不是以競賽為目標，學到 Level 2 即可 --- # FAQ --- ## 1. 我的目標是美國計算機奧林匹克競賽，但你們學生大多是在準備台灣資訊奧林匹亞，我也適合 AA競程 的課程嗎？ ---- * 不管是什麼樣的演算法競賽，考的內容都大同小異，基礎知識都是共通的。把「美國計算機奧林匹克競賽」換成任何其他演算法競賽答案也一樣。 --- ## 2. 你們的課程是針對哪個比賽的呢？是針對最近這一期的 APCS 做培訓嗎？ ---- * 再次強調，所有比賽的所需知識都是共通的，所以我們常態課程內容不會針對特定比賽，所有課程的目的都是長期的競賽相關知識培養。 --- ## 3. 我已經自學過圖論、動態規劃等 Level 1 課表上的知識了，那我是否該從 Level 2 學起呢？ ---- * 大多數人都會有自己在網上到處看看教學、看看別人的網誌介紹，自學讀完後就什麼都會的錯覺。 ---- * 根據我們教學經驗，多數在網上自學的人都只是學的一知半解。 ---- * 不信的話，請繼續看我們公開在 Level 1 的前導課程，看看教學內容是否都知道了，若大多數知識都不知道的話，強烈建議從 Level 1 開始學唷～ --- ## 4. 有沒有更客觀的方式知道我目前的程度呢？ ---- * 可在報名時填寫想要參加入學測驗的時間，從測驗結果就能由老師專業的評估你的程度了。 --- ## 5. 學競程入門班前有哪些預備知識是我該會的呢？ ---- * C++ 的基礎語法：運算式、條件語句、陣列、迴圈、函數等 * Online Judge 的使用方法 * 自定義函數以及內建函數的使用 * 浮點數的使用及輸入輸出 * C-style 字串 * C++ string * C++ vector --- ## 6. 上課是採取什麼樣的方式呢？ ---- * 網課目前是使用 Google Meet。 * 直接使用例題帶入要教的知識，可參考之後的試聽課。 * Level 0 的課程會留一些時間給大家嘗試寫每個知識的最基礎習題。Level 1 以後全程以講解知識為主，課堂中講解每道題之前都會預留些時間讓大家先自行思考，但不會讓大家在課堂上寫程式碼，必須課後自己花時間練習。 * 老師會點名學生回答問題。 * 上課時有問題可直接提問，老師會評估是否要立刻回答，還是課後再私下回答。 --- ## 7. 課後可以問老師問題嗎？ ---- * 課後若有問題可在 discord 詢問老師，老師有空時就回覆。 --- ## 8. 若我有些時段真的無法參加怎麼辦？ ---- * 我們會有課堂錄影，可自己找時間看錄播補起來。 --- ## 9. 有作業嗎？有的話作業是什麼形式呢？ ---- * 若目標是競賽，建議大家除課堂外，每週有至少 $8$ 個小時的時間留給競程 * 每題作業會提供參考難度，以及會分成四個組別 * 第一個組別的題目是最基礎的，若做不出來就代表你沒學會該知識。 * 第二個組別是建議下次上課前要完成的作業 * 第三個組別的題目比較進階，但仍建議整期課程結束後也要找時間補完。 * 第四個組別題目更靈活、綜合型更高，有餘力時再完成，可以再以後想複習知識時，再回來思考看看。 ---- * 我們並不會檢查大家是否有寫作業，但作業完成度以及考試成績將會是我們評估是否能上下一個 Level 的參考重點。 --- ## 10. 你們怎麼評估學生的學習成效呢？ ---- * Level 2 以前的課程每一期都有兩次考試，我們會用來考試結果來評估學生們的學習成效。 --- ## 附錄一： 免費語法自學資源 ---- * [從零到一：那些演算法競賽會用到的基礎語法(2020 年資奧國手撰寫的)](https://emanlaicepsa.github.io/2020/10/21/0-index/) * [Code 風景區：給新手的 C++ 教學(2016 年資奧國手撰寫的)](https://codingsimplifylife.blogspot.com/2016/04/c.html) --- ## 附錄二： 適合 Level 1 學生的練習平台 ---- ### 競程要怎麼練？ ---- ### 不就是刷題嗎！? ---- ### 先看一道數學問題 * 假設競程有 10 個基礎的知識點要學習，而某個練習平台剛好第 i 個知識點恰有 i 題，共 55 題，請問若每次都隨機抽一道沒寫過的題練習，要練到所有知識點所需的練習題數的期望值是多少呢？ ---- * 答案是 35 題左右 ---- * 但若有已經做完全部題的人幫你挑題目的話，只需要練 10 題！ ---- * 在競程上有個概念叫做「題單」，是由他人整理出來針對某個主題所列出的題目。 * 可想像成是數學課上某個單元的習題。 ---- ### 推薦新手練習題庫 * [CSES Problem Set](https://cses.fi/problemset/) * [配套的原文書籍](https://cses.fi/book/index.php) * [CS Academy](https://csacademy.com/) * [Atcoder](https://atcoder.jp/) * [Atcoder Problems Tool](https://kenkoooo.com/atcoder#/table/) ---- * 雖然我們課程會使用 [Codeforces](https://codeforces.com/) 這個平台，但並不推薦競程入門者在這個平台隨機挑題練習。 * 建議新手想練 Codeforces 上的題目時，可挑 Div. 3 和 Education Round 這兩個系列的比賽中的題目來練，這兩種類型的比賽是比較具教學和給新手練習的性質的。 * [tom0727'blog](https://tom0727.github.io/cf-problems/) 是仿造 kenkoooo 的網站架設的 Codeforces Problems Tool。 --- ## 附錄三： Level 1 課程相關的 ## 免費自學資源 ---- ### 請一定要記住，網上的教學也是錯誤百出，就算是一些乍看之下很厲害的網站也一樣 * 例如，[GeeksforGeeks](https://www.geeksforgeeks.org/) 常常有錯誤的教學文章 * 例子一：[Minimum edges required to make a Directed Graph Strongly Connected](https://www.geeksforgeeks.org/minimum-edges-required-to-make-a-directed-graph-strongly-connected) * 例子二：[Check if a given Graph is 2-edge connected or not](https://www.geeksforgeeks.org/check-if-a-given-graph-is-2-edge-connected-or-not/) ---- ### 中文資源 * [歷屆資訊之芽算法班講義](https://www.csie.ntu.edu.tw/~sprout/algo2021/) * 可更改網址上的年份，每年教學內容都不太一樣 * [2014 資訊之芽算法班課程總集](https://www.youtube.com/playlist?list=PLp5kjMAmhp--zNOYEwRUM2SovmzBQ8mTY) * [AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m) * 針對台灣的 APCS 檢定設計的教材，由中央大學退休教授吳邦一老師撰寫 ---- ### 英文資源 * [USACO Guide](https://usaco.guide/) * 這是由美國前 IOI 選手按照美國資奧選拔的考察知識點設計的教學資源匯總 * [CS Academy Lessons](https://csacademy.com/lessons/) * [Competitive Programmer's Handbook](https://cses.fi/book/index.php) * [Codforces Edu](https://codeforces.com/edu/courses) * [CP-Algorithms](https://cp-algorithms.com/)