# 清交資工 APCS 組備審、面試分享
## 前言
先上學測成績
國 : 14，英 : 15，數A : 11，自 : 15，社 : 13
可以看出我就是數學考很爛還妄想上資工系的笨蛋，還好資工系真的有給數學考爛的人走的路 : APCS 組(過一階最低的好像數A都只有 8、9 級左右)。
因為我覺得自己二階做得不錯所以就來分享了。
### 清大資工
學測成績(英 * 1 + 數A * 1 + 自 * 1) : 41 (20%)
審查資料 : 96 (40%)
口試 : 96 (40%)
總分 : 95
正取線 : 不知道但正取 3 個
結果 : 正取 1
### 陽交資工
學測成績(數A * 1) : 11 (20%)
審查資料 : 90.8 (35%)
口試 : 93.3 (45%)
總分 : 88.45
正取線 : 89.61，正取 5 個
結果 : 備取 2
## 審查資料
### 成績單
可以看出一件事，那就是我的在校成績是異常的爛。
### 個人資料表
把一些自己最得意的事蹟放出來，順便講一下課程學習成果在幹嘛。
### 學習歷程自述
#### 高中學習歷程反思
努力回想自己在高中關於資訊幹了啥，然後想辦法把他寫的很牛逼。
成績方面要想辦法從一坨不能看的成績當中抓出一些勉強能看的，然後做成圖表想辦法解釋那些波動。像我的段考成績相對於學期成績好很多，於是砸上 Excel 後發現自己高一有夠爛，高二跟高三好很多，然後我發現自己根本不知道為什麼，可能強者都去社會組了吧，所以只好掰說方法改了所以成績上來了。還可以找一些跟資訊有關自己又比較擅長的科目，像我寫數學 (其實看起來像一個數A 11 級的小丑在努力辯解自己數學其實沒那麼爛) 把一些比較出色的表現曬出來顯得自己好像很強一樣。
#### 就讀動機
寫說為什麼自己想讀資工系、為什麼自己適合資工系、為什麼要選這個學校的資工系。
##### 清大版本
##### 陽交版本
#### 未來規劃 (只有清大要)
畫大餅
### 課程學習成果
我們可能會發現學校的資訊課不能說是一點事都沒做，只能說是半點事都沒做。所以我們可以丟醫些好玩的東西上來，像是國文作文或短篇小說之類的。
#### 量水問題
高一數學與電腦課做的，但我忘了勾選 (勾選到底是哪個人想出來的陰間設計)，所以就用高三基本設計課以簡報模板的名義再傳一次。
有多個不同容量的杯子，要求最後使得其中一杯裝有所求水量並求出最短步驟，只有三種操作 : ​

把一個杯子裝滿水​

把一個杯子的水倒光​

把一個杯子的水倒到另一個杯子直到一杯滿了或空了​

我運用圖論模擬各杯子子間倒水，並使用 BFS 求出到達所求水量的最短步驟，最後利用我在基本設計課做出的簡報模板美化。
#### 醫聖吳沛恩
#### 仁者無敵
### 多元表現綜整
想辦法把多元表現分門別類，然後寫一些幹話顯得自己很強。
### 多元表現
APCS 觀念跟實作可以水兩個，剩下就把得獎紀錄丟上去，再看看自己課外幹了什麼跟資訊有關的都往上丟就對了 (社團、作品、營隊之類的)。
#### 110年建國中學資訊學科能力競賽 二等獎
#### 2021 NPSC佳作
#### 2021 HP Codewars 第四名
#### 111學年 建國中學資訊學科能力競賽 一等獎
#### 111學年 台北市資訊學科能力競賽 三等獎
#### APCS 觀念5級
#### APCS 實作5級
#### 建中資訊讀書會
#### APCS題解
#### 新型態資安實務主題課程 (AIS3)
## 面試
應該要帶的東西 : 身分證件、水壺 (講完會覺得很渴，現場又有飲水機可以白嫖冰水)
穿著 : T-shirt + 運動褲 (資工系沒有在管穿什麼的吧)
### 如何準備
除了自我介紹之外好像也沒什麼能準備的，畢竟我們又通靈不出教授要問什麼。

雖然我們不知道教授要問什麼，但是只要對自己超級有信心 (教授怎麼可能問到我答不出來的問題，如果出現了連我都答不出的問題那其他人就更加沒救了) 就可以發揮得很好。
### 清大
#### 流程
面試前 15 分鐘報到進等待室耍廢，接著會有人從等待是把你帶到面試教室，面試分兩間，每間各十分鐘。兩間都講完再填一個表單 (大概是跟面試體驗相關的) 就可以烙跑了。
#### 第一間
前五分鐘自我介紹 (要事先做好投影片上傳 google 表單，我因為忘了還被催繳)。接著教授會根據剛剛自介還有備審資料問一些問題。

場地 :
##### 自我介紹
各位教授好，我是建國中學的謝牧懷。

我是建中資訊校隊成員，曾經擔任我們資訊讀書會的講師，通過 APCS 觀念、實作五級檢測，並且被同學票選為班級優良學生。除此之外，我也參加學校的 1500 米長跑比賽，拿到高三第十名。

這些是我在高中三年參加程式競賽獲得的獎項。首先是獎狀不見的高一校內能競二等獎，雖然當時只抱著試試看的心態參賽，但沒想到打進全校前三十進入培訓。在培訓中我第一次接觸到演算法並切喜歡上了它，從此開啟高中的競程生涯。接下來三張是我在高二拿的獎，分別是校內賽二等獎、NPSC 團體賽佳作、HP Codewars 個人賽第四名。最後則是我高三拿到的校內賽一等獎和北市賽三等獎。

讓我學習資訊並且產生濃厚興趣的關鍵是資訊讀書會，這是一個教演算法的課後社團。我高一時作為學生聽課，到了高二我成為講師回饋讀書會。講師的工作主要有編講義、教課和出題，右邊這些是我教過的主題。這些工作中對我最有幫助的是編講義，在編講義的過程常可以發現一些主題中原本不曾注意到的細節，並且我會在每個例題後面附上自己的程式碼，除了給學生當參考解答外也可以鞭策自己練習題目。在今年的資訊讀書會當中我看到學弟繼承了我引進的新主題像是 Link-Cut-Tree 和 NTT，其中更是有學弟繼承了我每題附 code 的習慣。

另一個我利用資訊能力發揮影響力的地方是寫 APCS 題解。寫 APCS 題解的原因是網路上都沒人在寫，並且由於後測機制大家要等到成績公布才知道自己的解法是不是好的。我在吳邦一教授創立的 5000 多人社群 APCS 實作題檢測發布題解。我發布了五次 APCS 題解，總共 17000 次觀看。最開始只有我發題解，下一次就有三個人發了，現在平均都有五個人發題解，就算是學測前那一次我沒做題解也有六個人發了題解。

我練習演算法準備程式競賽的方法就是寫題目。這裡是三個我最常使用的 online judge，分別是 TIOJ 我寫了 172 題，Zerojudge 180 題，以及 CSES 我寫了 300 題中的 293 題，世界排名第 51。

我會想讀資工系是因為我很喜歡解題思考的過程，把 code 寫出來以後 de 出所有 bug 也會讓我獲得成就感。而我除了打演算法競賽之外也參加一些營隊增加我在資訊領域的廣度，右邊是我參加 AI 醫療營和資安實務營的證書。而最近 ChatGPT 和 AI 繪圖的崛起讓我感覺 AI 會在幾年內大躍進，對這個世界帶來巨大的影響，因此我認為現在是加入資工系學習 AI 技術的大好時機。清大資工吸引我的地方是這裡豐富的國際交流機會，這不只有助於拓展我的世界觀，更對於我以後如果想出國留學有巨大的幫助。

以上是我的自我介紹，謝謝教授。
##### 問答
Q : 你上了大學主要會想修什麼樣的課程?
我 : AI & 資安。

Q : 那你上了大學還會繼續打演算法競賽嗎?
我 : 不太會，會比較著重於專題製作。

Q : 資安那方面也有很多比賽，你剛也提到了你想要學資安，那你會去參加這些資安比賽嗎?
我 : 不會專門為了比賽去學或是花很多時間準備，會比較把比賽得獎當作學習的副產物。

Q : 從你剛剛的自我介紹跟備審中可以看出你對於教別人相當有熱枕，那你覺得自己學會跟要教會別人最大的差異在哪?
我 : 自己學會的最低標準只要會背模板能用就好，不需要知道原理跟證明。要教別人必須完全搞懂也要有證明才能讓學生更好理解而且可以回答大家的問題。

Q : 你對 AI 有什麼看法?
我 : 開始講我的 ChatGPT 使用心得，像是他能看懂我異想天開的文章之類的。
#### 第二間
進去可以抽兩個題目 (簡單的演算法題目，大概跟 APCS 第三或四題差不多的難度)，然後選一個想講的題目開始講如何解這一題，可以用旁邊的白板來輔助。

題目 :
1. 請解釋前序遍歷與中序遍歷。
2. 如何在給定前序遍歷和中序遍歷序列下建構出唯一樹?
3.
於是我開始在白板上畫樹講前序遍歷在幹嘛。
教授 : 你具體會怎麼實作?
我 : 表演白板寫 code 邊解釋我的 code 在幹嘛，寫出了一個遞迴前序遍歷。
教授 : 這是一個 recursive 的作法嘛，那你有除了 recursive 之外的作法嗎?
我 : 繼續表演白板寫 code，拿 stack 來實作前序遍歷。
教授 : 那中序的呢?
我 : 拿著剛剛畫的樹再講中序遍歷，再拿著前序遍歷的 code 修改成中序的樣子一邊解釋我的修改在幹嘛 (stack 作法那邊貌似少加了一個 else 判斷，會跑出無限迴圈)。
教授 : 你會怎麼用前序遍歷和中序遍歷序列構造出一棵樹?
我 : 前序序列的第一個就是根，在中序序列中找到他就可以分出左右子樹，然後把前序的開頭變成下一個，中序的左邊傳下去遞迴，回傳目前子樹的根再接上去就可以蓋出唯一一棵樹了。
教授 : 用前序遍歷和中序遍歷序列下建構出唯一樹的方法會有限制嗎?
我 : 只要他的序列給的是節點的編號不是什麼其他的東西就一定可以做到吧。(我這裡默認每個節點的編號都是不一樣的，花了一點時間解釋給教授)
### 陽交
#### 流程
面試前 15 分鐘報到開始到處逛街耍廢，時間到了自己去面試教室，面試七分鐘 (前一分鐘自我介紹，後六分鐘教授提問) 講完就可以烙跑了。

場地 :
#### 自我介紹
各位教授好，我是建國中學的謝牧懷。我是建中資訊校隊的成員，通過APCS觀念5級、實作5級檢測，我也被同學票選為班級優良學生。

我在高中三年參加許多程式競賽，除了在校內獲獎外，我也拿過 NPSC 團體賽佳作、HPCodewars 個人賽第四名、以及北市賽三等獎。

讓我學習資訊且產生濃厚興趣的關鍵是資訊讀書會。這是一個教演算法的課後社團。我在高一的時候作為學員聽課，到了高二成為講師回饋讀書會。我負責教的課程包括時間複雜度、DP、離線演算法、FFT、Link-cut-tree等。

我也在網路上發布 APCS 題解來利用我的資訊能力發揮更大的影響力。我已經發布了五篇題解，累積了17000次觀看，也帶起網路上大家寫題解的風氣。

除了打演算法競賽之外，我也修了線性代數和離散數學等課程。在大學我希望加入資工系學習 AI 技術跟上這個 AI 快速發展的時代。
#### 問答
Q : 在資訊讀書會做的講義當中你自己對哪一個最滿意?
我 : Link-Cut-Tree 那份，我覺得我 splay 的證明推得很好。

Q ; 哦，那可以講一下 splay 的時間複雜度要怎麼證明嗎?
我 : 講了一堆勢能證明然後說他均攤之後每次操作 $O(logN)$。

Q : 均攤複雜度跟平均複雜度的差別在哪裡呢?
我 : 拿單調對列舉例，說雖然可能有一次 queue 裡面所有東西都被 pop 出來，時間 $O(N)$，但是每個東西只會進去一次出來一次，所以總時間 $O(N)$，均攤每次 $O(1)$。平均複雜度是所有可能的操作時間加總取平均的時間複雜度，但可以一直丟 worst case 讓他的時間偏離平均，均攤則做不到。

Q : 那你覺得均攤每次 $O(logN)$ 的跟 每次一定 $O(logN)$ 的演算法哪個會比較快?
我 : 如果以單次來說我覺得每次都 $O(logN)$ 得比較快的機率比較大。

Q : 那如果樣本非常大呢?
我可能想了一下然後教授看時間所剩不多就說 : 沒關係，看得出來你是懂得。

Q : 你說你有修離散數學，那你對離散數學最有興趣的主題是什麼?
我 : 可能是生成函數吧。

Q : 你也有在資訊讀書會教過 FFT 嘛，那你知道 FFT 跟生成函數之間有什麼關聯嗎?
我 : 我他媽怎麼會知道(X 生成函數是無限次的多項式，FFT 能做多項式乘法，但不能做無限次的吧?
教授 : FFT 其實不只多項式乘法喔。然後時間就到了。

## 後記
後來我們班上的師大數學正取一跟我說他好像看過拿生成函數代複根再砸 IFFT 求係數，不愧是師大數學正取一，李宗憙的傳人。