前情提要
成大特選分成了初試跟上機考,到上機考這關總共還剩下20個人,而最後會錄取4個人。
神奇賽制
在考試開始後,他們發給了所有人每人一個隨身碟,其中包含5了個資料夾,分別代表5題。而在這5個資料夾中又分別有input、output、validator三個資料夾,分別存著輸入檔、我們要生出的輸出檔、驗證輸出檔與答案是否一樣的exe檔。exe檔只會有Accept跟Wrong Answer兩種結果,並且如果前面就Wrong Answer了就不會再往後跑了。在這5題中,大多數不是NP-Hard就是NP-Complete,要我們想辦法生出最佳化的答案,並給出計分方式。
在考完試後據學長的可靠消息指出,他們今年沒有找去年架cms系統的人,於是就自己想出了這種方法。
題目
PA 0-1背包問題
給你背包容量、每個物品的大小與價值,求選一些物品塞進背包後價值最大化。
背包容量 $\le 10^7$ ,物品數量 $\le 10^5$ 。
說實話我有點忘記這題的評分標準,只記得他說他是以greedy為基準,但沒講清楚,那個標準顯然很怪。而我這題全部測資都Accept但是0%,我在猜應該是做出了跟官解完全一樣的答案,然後我不知道他的評分方式在幹嘛所以就沒動了。
PB 著色問題
反正就是給你一張圖,要你以最少的顏色幫這張圖上色,使得任意相鄰兩個點顏色不同。
這題我就亂唬爛,每次選當前degree最大的點,然後用set維護他最小可以填什麼顏色,然後好像拿了90%(沒記清楚)。
PC 送禮物
給你一張有向圖,問任意節點走到任意節點的最短路徑平均長度(輸出浮點數到小數點後第三位)。
這應該是我最想抱怨的一題,然後後面有過的人其實應該大部分都要感謝我,我算是蠻早就開這題然後跟他們反應的,看到之後直接砸Floyd-Warshall,然後發現第一筆就錯了,接著就展開了幫出題者debug的任務,我先後大概叫出題者來來回回問了5個左右的問題。
- Q:有保證整張圖連通嗎? A:對。(但實際上並非如此)
- Q:我剛剛跑了一下,整張圖並非都連通,如果A不能走到B要算嗎? A:不用。
- Q:如果自己可以走到自己要算嗎? A:不用,誰會自己送自己禮物。(但實際上並非如此)
- Q:可是你的測資裡面有自環欸? A:我們再去檢查一下,自環就忽略他。(但實際上並非如此)
- Q:我剛剛測出來,你們如果出現自環的話答案會分子分母都加1欸。 A:我們再去確認一下。
然後過了大概快一小時,可能是後來太多人也問了,所以他們才公告了這件事。
反正這題我就不斷調整小數點後的誤差,在用input檔回去推算答案到底跟我弄的到底有什麼差,大概試了3筆左右才得出結論,事實也證明,出題者自己也不知道他寫了什麼跟測資生了什麼。
PD 專案測試
有人把他的程式分成了 $N (N \le 400)$ 個部分,有 $M(M \le 4000)$台機器,每台機器都可以測試一些部份的程式(集合),以及使用的花費,請你取最少花費的機器使得整個程式的所有部分都至少被測試到一次。
我用類似algorithm X的方法亂唬爛,但不知道是有地方沒寫好,還是其實這樣不可做,反正PC花掉我太多精力了,於是我就只有去生比較小的測資,所以這題究竟拿了幾分我也不知道。
PE 斯坦納樹
給你一些斯坦納點,要你求邊權最小的斯坦納樹。
這題我實在沒有好好開,因為是到最後匆忙亂寫的,跟PD一樣只有生一些比較小的測資,所以同樣地這題究竟拿了幾分我也不知道。
心得
大老遠從新北市跑去台南,結果只能說令我有點意外,整個寫下來都是在唬爛跟通靈,雖然我覺得這樣的賽制很驚喜很意外,但是做為一個特殊選材的考試來說問題相對有點多。出題者可能真的需要再想一下,不是在賽中讓我們幫你debug,同時也是要養成生測資寫valider的習慣,不然發生了自環是真的有點好笑。再來就是因為考了NP-Hard跟NP-Complete,導致非常難預估其他人的得分狀況,又或是每一題實際上可以拿到的分數極限在哪裡,間接也導致了解題時的順序跟猶豫要不要再往下做。