NCPC結束

今天是NCPC正式決戰的日子。從早上八點半過去，十二點二十開始比賽，下午五點結束，拖著疲憊的身體回到家中XD。

這次比賽我的戰果是兩題。根據計分表在結束前一個小時停止更新之前的記載，連我在內寫到兩題的總共有兩隊，而我是比較早達到兩題的，所以除非有人可以在剩下的一小時內瞬間寫出兩題（只趕出一題變成兩題是不行的，我會以時間差關係獲勝），否則沒有意外的話我應該是全國冠軍吧（謎之聲：乙組明明只有六隊來比，還要號稱什麼「全國」冠軍，而且kochi那些強者都沒來....）。至不濟也是亞軍或是季軍。

這次的題目第一題很明顯是免費奉送的白爛題，題目我也忘了，反正三四十分鐘就解開了，到時候題目放出來的時候再Update這篇好了。第二題是基因最長序列，給定一個DNA序列，找出這段序列中的最長重複片段以及其重複的次數以及首次出現的位置，召喚萬能的STL函式庫，DP下去就結束了。

不過我的好運到此為止，剩下的幾題之中，有兩題是我當時在猶豫要做哪題的。一題是繞圈圈比數字遊戲：有很多人拿著互不相同的號碼牌圍成一個圈，每次任意選一組相鄰的兩人進行「戰鬥」，如果兩人號碼牌和為偶數，則數字小的人出局，如果號碼牌和為奇數，則數字大的人出局，接下來一直選人一直淘汰，直到剩下兩人。而選取戰鬥的順序不同，最後剩下的人就可能不同。題目就是要求給一串名單，問這串名單所有可能的最後剩下人數有幾種變化。這題我犯了非常嚴重的錯誤，直接給他暴搜下去，在最大人數N=1000（還是100？反正意義都一樣）的情況下當然Time Limit Exceed（直到回到家，我才想起高中時的經驗，N=15左右DFS就會開始明顯變慢）。這題的解法我事後想想應該是某種很特殊的DP（10/24 update：其實這樣好像也不對>"<），從只有兩人的Base case一直推導到N=1000。因為其實相同剩下人數的不同序列，只要他們的奇偶排列相似，那麼最後結局其實會類似，而不是像我一樣在比賽中堅持暴搜，還花光時間進行自以為是的剪枝。不過現在比賽結束了，我變懶沒動力真的把它完成XDDDD。

另外一題是比賽後我覺得當時應該選的，題目是給定一組特殊的方程式：
x1+x2+x3+....x(m1)=c1 mod p
x(m1)+x(m1+1)+....+x(m2)=c2 mod p
....
x(mk-1)+....+x(mk)=ck mod p

題目會給N、K、P、還有C。MK=P，K是每行有幾個X，P是質數，C是餘數，但其實C沒有意義。這題我看到後兩分鐘就想通了，其實題目只是變形的大數運算而已，最大的答案大概是10的一百次方左右。只要code出大數，然後用基本排列組合暴解就可以了。可是那時在「DFS暴搜（結果根本不是）」和「寫大數」之間，我很白爛的花了好幾個小時選了前者。事後想想，如果我把時間拿來寫大數，搞不好我今天是三題而不是兩題。

這次寫題目的感想是：STL真的超棒。只要想比賽，STL就一定要學好。雖然學STL要花上一點時間。可是當STL大概用熟，哪天寫程式或是寫考古直接用他寫好的queue輕鬆BFS時、或是沒辦法開大陣列跑DP，但因為有STL可以輕鬆的用map、multimap搞定事情時、還有用vector很輕鬆的取代陣列，完全不必理會segmentation fault還有指標遊戲的時候，一定會非常的感謝STL。這次比賽前我決定花一些錢搞定STL的書，結果在會場上幫助實在是太大了（我的code每題都是一大堆STL）


這次比賽還有考古題的檢討，分類的話大概有幾點。第一點是書要看熟，很多數學的東西我沒有底子，所以解題就很慢，甚至萬一碰到像去年乙組考古考Cubic curve fitting我就完全爆炸，機率與統計的東西也是，未來有時間就看點數學書吧XD。第二個是我對題目的經驗還是太少（早知道高中就少玩一點MUD還有毀滅戰士，不過那樣的話搞不好我現在是在念資工），N=1000我竟然還想暴搜，事後想想實在是非常離譜。就設法從ACM入手吧，然後搭配類似ITOA等書慢慢學。我想我應該會更注意DP，因為我發現我一眼看出DP的能力似乎不太夠，而且我對這個技巧有興趣，話說那是我高中進入資訊社學的第一個技巧XD

剩下我沒提到的題目有一題是考類似Compiler的東西，給定一個已經製作成樹狀的code，然後找出哪段code永遠不會被執行。雖然我對Compiler有興趣，可是相關的書我一本都沒看，看了一段時間想不出來就放棄了，另外有一題是給定空間高度和齒輪大小，然後想辦法按照他的要求排齒輪，現場我沒想出來。

另外一個我覺得不足的地方是自己還不夠沉穩，事後想想如果我更沉穩的話，比賽表現也許會更好。不過這個就比較長遠了。今天早上測試機器的時候，我緊張到根本沒把測試用題目看清楚就開始寫，連陣列反轉這種東西都會寫錯。我的指導老師徐老師立刻指出我心情過於煩躁浮動的弊病，為了安撫自己，我還特地拿原子筆在左手手背寫個大大的「靜」字，也是有發揮一定的效果啦。搭配早上喝的奶茶和咖啡，以及途中去外面瘋狂吃點心，對煩躁的心情也有一定的幫助XD。

說到點心，點心的的內容和四年前一樣，和當年我來一樣的地方，來比資訊奧林匹亞國手入營考時一樣，洋芋鰻魚、布丁、燒賣、巧克力蛋糕等等，勾起了我很多的回憶。當初聯考前一兩個月還是不曉得多久，忘了，我和得力抹還有皮特一起來參加國手入營考，結果他們倆個考上了，我卻因為怯場（總之就是遇到比賽會很不穩定），連Blacksmith一個bubble sort就可以解決的問題都寫錯。加上那時候是時間到了只能測試一次，而不是像這次一樣錯了可以死命重來，總之就是爆了，後來和媽媽間又發生了一些互動，讓我決定去考醫學系。如果當年那次比賽讓我贏了讓我在聯考前跑去資訊國手營，可能我就不會來到現在的學校認識現在的同學。

話說回來，這次的比賽得力抹和皮特也有來比，得力抹看起來還是一副鳥樣。皮特由於很久沒見面，我剛看到他的時候還認不出來，直到得力抹指點我他有來，我才在比賽結束以後找到他，然後問「你是台南一中畢業的嗎？」「是的」「那你是皮特嗎？」「是的」認出他來。不過他們都是甲組，而我是非資工的乙組，所以不能和他們再一次決鬥，真是可惜XD（謎之聲：你明明可以報甲組，只是你這個人貪圖獎金......）

另外一些小插曲就是早上到校還有環境測試的部份，這次比賽環境是Suse Enterprise Desktop，總之就是討厭的Linux，他們Eclipse + CDT一開始還沒有灌好，害我用terminal開vi然後用g++解決問題。（不過後來我找到gedit）。

四周其他隊伍突鎚的狀況也十分多，有好幾隊根本沒有在賽前使用過Eclipse，連選Managed C++ Make Project都不知道，當然在場我是基於運動家精神以及徐老師的鼓勵去幫忙，不過IDE這種東西本來就應該在比賽前熟悉，連這點都沒做實在不好。比較有趣的是我看到一隊很神奇的打開了我不會用的terminal，講解複雜的vi，可是打出來的程式碼沒有縮排<'囧`>，不過他們那隊三個人後來也是有兩題，也不算弱了（謎之聲：又是小踢先生擅長的 提高被擊敗對手的身價間接稱讚自己的絕技）。

另一個比較有趣的事情是今天早上我媽說想載我去，我答應了（為了美好的母子聊天XD），結果我媽跑錯，跑道和平東路二段的129號，可是我要去的是一段的129號，還好路徑是直線，我沒有迷路加上時間也很早，所以沒出問題XD。另一個有趣的事情是早上試機的時候即使我極度浮躁，錯誤連連，徐老師仍然對我的程式設計十分讚賞，問我要不要畢業後直接考博士XD。（真的有隔行如隔山的感覺，我的程式設計其實應該只是中下吧，可是到醫學的世界就變成高手orz）

不過比完了還是要回到現實世界啊。雖然非常期盼比賽的結果，可是日常生活該做的事還是要做，禮拜一要簡報藥理PBL所需的資料，禮拜四要抽考寄蟲還要交一千兩百字的無卵頭家報告，十月底要考病理學，我還欠系學會電子通訊錄系統，事情還多得很呢！ 全文連結