<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
# 2025 Introduction to Competitive Programming
2025/9/15
---
## Course Administration
### course link
- https://hackmd.io/@LeeShoWhaodian/2025pretrainingAutumnSyllabus
### Coach
- I don't know
### Co-Coach
- IDK either
### Lecturer
- 陳上恩 (Discord: \_shanc\_)
- 胡智涵 (Discord: zihan8130)
- 陳宏勝 (Discord: .\_.asd)
----
## Course Group Link
https://discord.gg/uaBpzZJWhN
---
## 什麼是競程?
- Competitive programming :
競賽程式、競技程式、程式設計競賽，簡稱競程
- 給一些電腦科學 (資工) 常見的問題，用最快的速度解掉
- 使用 (or 設計) 資料結構與演算法去解決問題
- 團隊合作💪
<!-- .element: class="fragment" data-fragment-index="1" -->
----
## 參加程式設計競賽有什麼好處?
- 增加程式設計能力
- 碩士推甄、工作面試更容易應對
- 吃很多好吃的
- 拿贈品
- 到處比賽順便去玩
- 出國玩
- 程式設計、資料結構、演算法輕鬆過
----
## 碩士推甄、工作面試更容易應對
碩士推甄需要比別人更優秀的備審資料
如果有參加過競賽有優異的成績則能比別人更有機會更前面的推甄名次
工作時很常會考演算法白板題，對於打過競賽程式的選手來說非常的吃香
----
## 吃很多好吃的
比賽中會有很多好吃的點心
蛋糕餅乾飲料等等
通常都很好吃要用搶的
<div style="position: absolute; left: 7%; top:100%;">
</div>
<div style="position: absolute; left: 60%; top:100%;">
</div>
----
## 拿贈品
* 獎金、禮卷、虛擬貨幣
* T-shirt *9
* 背包 *4
* 鍵盤 *1
* 電腦 *1
* ...
(以上為 jakao 於大學期間獲得的)
<div style="position: absolute; left: 7%; top:100%;">
參加線上比賽很多都會有不斐的獎金獎品
</div>
<div style="position: absolute; left: 70%; top:27.5%;">
中區程式設計競賽前三名獎品
</div>
----
## 競程怎麼比
- 使用程式語言在比賽中解決 10-15 道的問題
- 比賽時間 5 小時
- 三人一隊
- 答對一題會有一顆氣球🎈
----
## 解決問題
每個問題會有明確的問題定義、技術規格、程式輸入與輸出
----
## 你會需要...
有個非常熟練的程式語言 (C/C++, Java)
<!-- .element: class="fragment" data-fragment-index="1" -->
數學與英文
<!-- .element: class="fragment" data-fragment-index="2" -->
思維能力
<!-- .element: class="fragment" data-fragment-index="3" -->
熟悉資料結構 & 演算法
<!-- .element: class="fragment" data-fragment-index="4" -->
----
## 有個非常熟練的程式語言
- C++
- 宣告、判斷、迴圈、陣列、遞迴、結構...
- STL (Standard Template Library)
- Lambda, C\+\+14, C\+\+17
----
## 數學與英文
- 高中數學、離散數學、線性代數 (解題)
- 英文閱讀、理解
- 看懂題目、讀題更快、不看錯題目
- 學新演算法閱讀英文文章
- 比賽題目題解
----
## 思維能力
比賽除了考演算法資料結構等等題目、還會有單純的思維題，
包括閱讀理解題、找規律題、想法題、通靈題、梗題等等。
----
## 熟悉資料結構&演算法
水題(簡單題)、思維題頂多出個 3~6 題，剩下的題目都是算法題
也是最重要的，以及我們這 1~2 年會教的內容
----
<div style="font-size:10px">
<div style="position: absolute; right: 10%;">
- Tree
- Lowest Common Ancestor
- DP on Tree
- DSU on Tree
- Heavy-Light Decomposition
- Graph
- DFS/BFS
- Shortest Path
- Minimum Spanning Tree
- Topological Sort
- SCC/BCC
- 2-SAT
- Matching
- Flow
- Eulerian Path
- String
- Trie
- Hash
- KMP
- Zvalue
- Manacher
- Suffix Array
- Palindrome Tree
- Geometry
- Convex hull
- Sweep Line
- Closest Pair
- Bipartite Match & Flow
- Matching
- Weighted Matching
- Max-closure
- PS Problem
- KM (Hungerian)
- Max Flow
- Min Cost Flow
</div>
- Brute Force Search
- Backtracking
- Memory Search
- Meet In the Middle
- Binary Search
- Greedy and Sorting
- Divide and Conquer
- Math
- Modulo Operation
- Modular Multiplicative Inverse
- Prime
- Dynamic Programming
- Knapsack Problem
- LCS
- DP on DAG
- Stack / Deque
- Bitmask DP
- 1D/1D Dynamic Programming
- Data Structure
- Segment Tree
- Sparse Table
- Treap
- Persistent Data Structure
- Square Algorithm
- Square Root Decomposition
- Mo's Algorithm
</div>
----
## 3-semesters-course Overview
1. Introduction to Competitive Programming Pretrain (now)
- useful coding skill & basic algorithm
2. Introduction to Competitive Programming (next semester)
- basic algorithm
- virtual contest (weekend)
3. Advanced Competitive Programming (next year)
- advanced algorithm
- virtual contest (weekend)
---
## 高中比賽 vs 大學比賽
- 高中以個人賽為主，大學則是 3 人一隊五小時
- 高中 IOI 賽制通常每題會有子題分數；
大學通常為 ICPC 賽制，每題只有通過或答錯，沒有子題分數
- 大學比賽可以攜帶最多 25 頁的單面 A4 程式筆記 (codebook)
- 大學比賽題本為英文
----
## 比賽排名
高中比賽通常只比分數高低
而大學比賽為比解題數，再比penalty
那 penalty 怎麼算?
每題解出來的時間總和加上答對的題目所錯的次數*20
以此記分板來看 penalty 為 35 + 7 + 2*20 = 82
----
## 各種比賽
- NCPC
- ICPC
- TOPC
- CPE
- 東華盃程式設計競賽
- 中區程式設計競賽
- HP Codewars?
- ~~北區程式設計競賽~~
[見連結](https://hackmd.io/@jakao/collegiateCompetitionsProgramming)
----
### NCPC
大專程式設計競賽
分成初賽與決賽
初賽為校內初賽，每校取最多六隊晉級決賽，時間三小時
決賽五小時
獎項有以下（每校最多兩隊得名）：
- 一個第一名(10w)
- 兩個第二名(5w)
- 三個第三名(3w)
- 五個第四名(1w)
- 佳作（20-30隊左右）
https://ncpc.nsysu.edu.tw/p/412-1062-99.php?Lang=zh-tw
----
## TOPC
Taiwan Online Programming Contest
- ICPC預賽
- 3小時
- 約 8~10 題
https://topc.icpc.tw/
----
## CPE
大學程式能力檢定
- 個人檢定
- 3小時七題
- 取得 ICPC 門票之一 (三人一年須參加至少3/4次)
https://cpe.mcu.edu.tw/
----
### ICPC
國際大學生程式設計競賽
台灣區取1-2校晉級世界決賽
今年新規則，聽說台灣可能有6-10隊可以參加playoff爭取額外門票
獎項 (累計至 2022)
- 10隊金牌(等各位努力爭取第一面)
- 20隊銀牌(累積2面，2020, 2022)
- 30隊銅牌(累積13+面)
參加就能拿到 T-shirt 和包包 (Maybe)
----
ICPC 門票取得（總共 100 隊）
- TOPC 每校各一隊（約 20~30 校?）
- NCPC (擇優前 40 隊?)
- CPE 每校最多兩隊 10 隊
- 私校盃、科大杯各 10 隊
- 剩下名額 TOPC 遞補?
----
## 總體而言大概是醬
<!--  -->
<!--  -->
----
## 隊伍組成
三個人一隊，隊上組成應該需要有...
- 一個讀題速度快且不會看錯題目的
- 一個負責上機寫 code 的
- 打字速度快負責抄模板的(WPM 50-60 up)
打字練習網站
https://play.typeracer.com/
https://monkeytype.com/
----
## 隊伍團練
- 多一起打練習賽
- 有題目不會，先跟隊友討論解法
- 解完題目互相分享討論
- 多看隊友的 code
- 跟隊友統一 code style
- 平時多聊天、揪吃飯培養默契 (optional : 多吵架)
----
## 個人訓練
#### 題單
- [CSES](https://cses.fi/problemset/)
- [算法竞赛入门经典(第2版)](https://vjudge.net/article/45)
#### 周賽
- [Atcoder Beginner Contest](https://atcoder.jp/contests/)
- [Leetcode Weekly Contest](https://leetcode.com/contest/)
#### 更多競賽網址
- [Codeforces](https://codeforces.com/contest)
----
## 億點點自學資源
- [從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/)
- [USACO guide](https://usaco.guide/)
- [CSES book
](https://cses.fi/book/book.pdf)
- [演算法筆記](https://web.ntnu.edu.tw/~algo/index.html)
- [Codeforces Course](https://codeforces.com/edu/courses)
- [Algorithms for Competitive Programming
](https://cp-algorithms.com/)
- [資訊之芽](https://www.csie.ntu.edu.tw/~sprout/algo2016/)
- [建中講義](http://pisces.ck.tp.edu.tw/~peng/index.php?year=2015)
- [ap325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m)
---
Any Questions?
{"contributors":"[{\"id\":\"4f67a8cd-06ae-45dc-a8e3-62c6a41e5a37\",\"add\":10492,\"del\":3994,\"latestUpdatedAt\":1764251441056}]","description":"2024 / 2 / 21","slideOptions":"{\"type\":\"slide\",\"slideOptions\":{\"transition\":\"fade\"}}","title":"2025 Introduction to Competitive Programming","image":"https://hackmd.io/_uploads/rkj4DRC9ge.png"}