<style>
.reveal .slides {
text-align: left;
font-size:30px
}
</style>
# 大學競賽程式介紹
----
- 什麼是程式設計競賽
- 高中比賽 vs 大學比賽
- 年度大比賽
- 隊伍組成
- 個人培訓
- 總結
---
## 什麼是程式設計競賽?
競賽程式、程式設計競賽，簡稱競程
- 使用程式語言在比賽中解決 10-15 道的問題
- 比賽時間 5 小時
- 三人一隊
- 答對一題會有一顆氣球
----
## 解決問題
每個問題會有明確的問題定義、技術規格、程式輸入與輸出
----
## 你會需要...
<span>- 有個非常熟練的程式語言(C/C++, Java)<br><!-- .element: class="fragment" data-fragment-index="1" --></span>
<span>- 數學與英文<br><!-- .element: class="fragment" data-fragment-index="2" --></span>
<span>- 思維能力<br><!-- .element: class="fragment" data-fragment-index="3" --></span>
<span>- 熟悉資料結構&演算法<br><!-- .element: class="fragment" data-fragment-index="4" --></span>
----
## 有個非常熟練的程式語言
- 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
- KM
- 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>
---
## 高中比賽 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.ntnu.edu.tw/index.html
----
### ICPC
國際大學生程式設計競賽
台灣區取1-2校晉級世界決賽
今年新規則，聽說台灣可能有6-10隊可以參加playoff爭取額外門票
獎項
- 10隊金牌(等各位努力爭取第一面)
- 20隊銀牌(累積2面，2020, 2022)
- 30隊銅牌(累積13面)
參加就能拿到 T-shirt 和包包
----
ICPC 門票取得（總共100隊）
- TOPC 每校各一隊（約20-30校）
- NCPC 前40隊
- CPE 每校最多兩隊10隊
- 私校盃、科大杯各10隊
- 剩下名額 TOPC 遞補
https://icpc2023.ntub.edu.tw/?page_id=78
----
## TOPC
Taiwan Online Programming Contest
- ICPC預賽
- 3小時
- 約8-10題
https://topc2023.icpc.tw/
----
## CPE
大學程式能力檢定
- 個人檢定
- 3小時七題
- 取得 ICPC 門票之一 (三人一年須參加至少3/4次)
https://cpe.cse.nsysu.edu.tw/
----
----
## Competitive Programming Team Hall of Fame
http://www.deepsea9.taipei/index.php/advanced-computation-laboratory/competitive-programming-team-hall-of-fame/
----
## 隊伍組成
三個人一隊，隊上組成應該需要有...
- 一個讀題速度快且不會看錯題目的
- 一個負責上機寫 code 的
- 打字速度快負責抄模板的(WPM 50-60 up)
----
- 一個讀題速度快且不會看錯題目的(多練、可以帶字典)
- 一個負責上機寫 code 的(恩，多練)
- 打字速度快負責抄模板的(多打字、平常多練習抄模板)
打字練習網站
https://play.typeracer.com/
https://monkeytype.com/
----
## 隊伍團練
- 多一起打練習賽
- 有題目不會，先跟隊友討論解法
- 解完題目互相分享討論
- 多看隊友的 code
- 跟隊友統一 code style
- 平時多聊天、揪吃飯培養默契
----
## 個人訓練
#### 題單
- [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)
- [Codechef](https://www.codechef.com/contests)
----
## 學習資源
- [從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/)
- [AP325](https://drive.google.com/drive/u/0/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m)
- [演算法筆記](https://web.ntnu.edu.tw/~algo/)
- [CSES CP book](https://cses.fi/book/book.pdf)
- [CP Algorithm](https://cp-algorithms.com/)
- [OI wiki](https://oi-wiki.org/)
----
## 比賽策略與準備
- https://zhuanlan.zhihu.com/p/438790068
- https://hackmd.io/@sa072686/rke70TNtX?type=view
----
## 加入團隊的好處
- 校內正式比賽供餐
- 出去比賽提供報名費餐點、住宿
- 練起來的話理論上程式設計課、資料結構、演算法課都能輕鬆過
- 工作面試考白板題能輕鬆應對
----
## 加入團隊的缺點
- 練競程要練到好，非常花時間，可能會犧牲掉其他休息時間
- 團隊練習會占用到晚上 & 假日(週六)
- ~~認識很多怪人~~
{"contributors":"[{\"id\":\"19f09ccf-6b99-452f-971f-955cfc1657f3\",\"add\":10185,\"del\":5173}]","description":"一場五小時 10~15題","title":"大學競賽程式介紹"}