成大資工甲組 特殊選才心得

特選之旅還在進行中，如果想看其他間的面試心得還有結果，可以查閱特選心得彙整

前言

成大資工特選分為兩個組別：甲組（演算法）、乙組（開發），各有 4 個名額，且複試都是採取上機考的方式，最終成績算法為甲組備審 / 上機考 50、50，乙組 20、80。

甲組複試時間是 11/19，10:30 開始報到、11:00 測機、13:30 ~ 16:30 考試。在測機的時候因為網路沒關，所以我就以為可以裝插件，因此就下載了 code runner 還有 One Dark 的主題（現場有提供 VS Code），，結果後來才得知其實是他們忘記關了，回來之後那些插件就通通被他們刪掉了：（。

賽制

今年的賽制是很特殊的，雖然一樣是有部分分，但有別於以往比賽的 OI、ICPC 制，幾乎都是考有”標準答案”的題目，這次考的是「最佳化演算法」，題目本身幾乎都是 NP-Hard 問題，以現今的電腦沒有辦法求出標準答案，因此算分方式是依照你寫得夠不夠好來評分，答案越接近官方準備的最佳解，分數就越高，會利用題目提供的公式算出一個 % 數（因為官方也無法求出真正的最好答案，所以是有可能超過 100 % 的）。

除了題目本身很特殊以外，評測方法採取的是全 output-only，題目所有的測試資料都會附在題目裡，在賽中需要將程式輸出的結果放進資料夾中，最後會用 output 資料夾中的檔案去跟官方提供的答案比較。

據主辦方所述，由於計分方式特殊的關係，他們無法將這些題目放到 Online Judge 上，因此在每一題的檔案中，都有一個用於驗證輸出檔的可執行檔（.exe），當我們生成完答案之後，可以自己在本機評測，看看自己拿到了幾 %。但賽中所知道的 % 數其實也不是最終的成績，賽後每一題都會將參賽者的完成程度排名，然後再依照排名給分，所以如果有一題最高就是 50%，那麼那個人就會拿到該題的滿分。

題目

PA：超大背包問題 - 0%

基本上就是 0-1 背包問題，但是範圍超級大，所以無法使用傳統的 DP 來做，據說可以限制範圍，在某個範圍以內使用貪心，然後再使用 DP 填充剩下的重量，但我賽中沒有做出來，因此沒拿到分數。

PB：n 分圖問題 - 0%

n 分圖的定義是，將每個點畫成 n 種顏色，如果每條邊所連接的兩個點顏色都不相同，那麼這張圖就是一個 n 分圖，題目目標是要找到一個最小的 n。

我的作法基本上跟其他有撈到分數的人都一樣：在 DFS 的過程中去貪心分配每個點的顏色，但我不知道哪裡出錯了，最後還是 0%。

PC：平均最短路 - Accepted

這是唯一有標準答案的題目：有一張有向圖，求對於所有滿足 u 可到達 v 的點對 (u, v)，求出其最短路的平均值，點數 = 100。

這題算是最水的一題，直接用每個點當起點 BFS，然後暴力枚舉點對，最後算平均值即可。

但是這題有一個很大的陷阱：如果有自環的話，那麼就需要考慮 u = v 的點對（印象中題本是寫另外一個點啊…），所以如果沒有算到自環的話，答案就會偏離 0.001 ~ 0.002。起初我以為是浮點數的誤差，因此就手動將每個答案都加上正負 0.001 or 0.002，然後再去跑驗證程式，就 AC 了 hehe，賽中才知道是自環的問題。

PD：集合問題 - 99.86%

有數個集合，每個集合中有一些數字以及一個權重，要求選出一些集合，使得這些集合的聯集包含所有數字，且權重和最小。

這題我一開始在思考是否能用背包的概念去思考，但寫了許久一直沒有突破，在時間壓力下我直接使用貪心，將每個集合利用權重由小到大排序，接著一個一個掃，如果加入這個集合能夠讓聯集大小增加，那就加上去，沒想到就拿到 99.86% 了@@，不知道有沒有人拿到 100%。

PE：斯坦納樹 - 0%

這題我沒有看，根據其他人的描述：給一張圖和指定點集 T，求包含 T 的最小邊權和斯坦納樹。

最終成績

最後是拿到了原始分數 40 分的成績，由於 PD 是 99.86%，所以不意外的話最終成績應該也不會差太多，就看到時候放榜如何了。

心得

這次的賽制很有趣，脫離了高中比賽的題型，改成較貼近實際生活中會遇到的最佳化問題，這個方向我覺得是好的，或許可以選到更不一樣的人才，但我也觀察出了幾個問題：

1. 根據上面的描述可以發現到，其實題目本身還是偏向於學術研究的類型，並沒有比較貼近於生活，甚至容易有一種在寫論文題的感覺。結果便是更加劇了考生狀態的起伏，這樣是否有可能會讓成大反而沒招到他們想要的人呢？（當然這是建立在我認為成大想要較貼近現實的猜想，或許他們另有想法，我單純提出了我的擔憂）
2. 題目是 output only，需要利用 freopen + loop 或是其他類似作法來讀檔案，這個在考試辦法規定時可以看得出來，但 PB 由於某些緣故（可能是有字串，或是藏了什麼奇怪的不可視字元），導致整題是沒有辦法利用迴圈讀檔的，我問到的所有參賽者都有遇到這個問題，都造成了不少的時間損耗，像是我就至少花了一小時在尋找無法迴圈讀檔的原因，最後也花了不少時間在複製貼上測資當中。這個問題相比於一般比賽中會出現的測資太弱，我認為是更嚴重的，假設出題者有驗題，那他又是怎麼讀檔的呢？難不成本來就希望我們複製貼上測資嗎？
3. （11/21 更）據說 UTF-8 以外的編碼格式是無法被讀取的，這件事似乎沒被公告過，主辦方好像也不知道這件事，導致參賽者會因為編輯器預設編碼的差異而拿不到成績（有的參賽者是利用編譯參數，如 ./a.exe > 1_out.txt，而這樣出來的編碼格式會是 UTF16LE 或是其它種），這就又衍伸出了另外一個問題：在參賽者不知道編碼格式會影響評判程式的情況下，再加上主辦方沒有提供統一的讀檔方式，參賽者便無法知道自己的編碼格式是錯誤的，一定程度的影響了比賽公平性。

撇除掉上述的問題，我覺得主辦方做得不錯了，新的賽制也十分新奇。但或許是題型的少見，導致幾乎全場燒雞，這點是比較可惜的。如果明年要繼續辦理這種賽制，希望可以在細節上做得更完整，才能夠真正的發揮出這個賽制的價值。

一些小小建議

根據新聞報導，成大資工希望透過上機考來招收能夠解決實際問題的人才，而這或許也是採用這種賽制的原因，因此學習演算法千萬不要只停留在解題上，也要多多思考如何將演算法應用在實際問題中，如果能夠將演算法及實際情境融合，那麼不管是在學術上或是實務上都會有很大的幫助。（但這好難 QQ）