| layout | title | date | tags | ||
|---|---|---|---|---|---|
post |
教育部100年度全國電腦軟體設計競賽 (2011 NCPC) |
2011-10-16 |
|
今天又是一年一度的 NCPC，這是我第三次參賽了，這次跟兩個大三學弟一隊參賽，話說比了三次，三次的組員都是完完全全不一樣。 -___-"
一如往常的賽程，測試機器 ➔ 吃午餐 ➔ 正式比賽 ➔ 回家。最後結果只解出六題，其實心中五味雜陳，對自己這樣的成績其實覺的還OK了。從上次比完 ACM-ICPC 吉隆坡賽區後，就幾乎沒在練習 ACM 了。之後都是忙 EDA 還有混日子，曾經有過不堪的往事，使得我對 ACM 的熱誠也幾乎沒有了。但還是喜歡研究些演算法跟資料結構，但不會有大二那段不眠不休了練習光景。
這次本來也不打算參賽，主要是之前的隊友不想比了，所以可能湊不到人。後來聽說有兩個學弟因為另一個人去跑迎新，所以無法參賽，所以我就加入他們陪他們一起比。就當作是帶學弟比賽，順便跟他們分享些經驗，教他們些東西。
但對於比賽結果也非常不滿意，主要是又輸給了我最不想輸了人。我知道自己其實真的沒有他厲害，輸給他早有心裡準備。但就是今天比賽的過程太過順暢了，雖然贏不過北部的高手們，但至少在封榜一直維持在自己學校的第一名。除了 Problem D 之外，也就是我所解出了六題，全部都是一次就 AC。比賽到現在，第一次這樣…。Problem D 大概從第二個小時就寫好了，但怎麼改怎麼傳都是 Wrong Answer，這題就這樣一直卡到比賽結束，大概花了有兩個小時在這題上面了。
由於這題輸入測資的方式，我決定使用 gets + strtok 的方式來讀測試資料。在電腦上，怎麼測試都是對了，當然這情況常發生沒甚麼。到了比賽結束才聽說，在切割字串時，要把 \r 也加入切割的參數裡面。基本上對於在 Linux 上出現這樣的測資是有點無言。但這個只要改成用 scanf 慢慢處理就可以解決，我最嘔的就在這裡。比賽中，我曾經要把 code 改成用 scanf，但快改完時突然又覺的應該不是這個問題。所以又改回 gets + strtok 的方法繼續嘗試。我很氣自己，為什麼沒有先上傳一次看看。
就因為這樣，我們在封榜這段時間被同校的另一個隊伍追過了。唉，真是有種天堂掉到地獄的滋味，為何讓我順暢了四個小時，再讓我在最後一小時墜落。或許，這就是命吧。
大概是最後一次參加 NCPC 了吧，比了三年。回想第一次比賽，什麼都不會只會 BFS 跟字串切割（strtok，今天也是被他害死的）就去比賽了。結果解了兩題超慘，不過竟然有出一題 BFS 就可以解的題目。解出的另一題用暴力解的，但聽說這題照理講暴力解時間複雜度會爆掉，學長們聽說也很驚訝。第二次參賽是經過一整年電子哥的培訓，加上自己全心全意的衝刺，忘了解出幾題，竟然得到第二名。說實在的，真的很驚訝。再來是這次，這次就是頹廢了快一年，但能解出六題我自己也滿驚訝了。大概是靠以前太吹毛求疵的整理 code 做 template，今天比賽幾乎都是看著自己的 template 在寫。所以，好好整理 template 是很重要的！
接下來還有 ICPC，但我專題進度零，老闆也給了我壓力，再不做不行了。 ICPC 大概也要毀了。這次的比賽成績，很幹，真的。難過，真的。我沒有把改成 scanf 的版本 submit。如果我多試這麼一次，結果大概就不是這樣了。是我對不起我的隊友們。
另外，補充一下今年題目大概的類型。詳細題號有點忘了，大概只有 Problem D 忘不了，等有題目出來再來補一下。但題目也沒看完，竟然有兩題完全看不懂要幹嘛。:(
這次比賽我大概只看了一題，其他都是隊友看的，他們看完直接跟我講題目跟他們的想法，若是可行我就直接寫這樣。我大概就看了解方程式的那題而已。
第一題
第一題解了一題 LIS，基本上大概看一下測試資料就知道了。但要注意 n 的大小，我記得好像有到 100000 這麼大，所以得用 NlogN 的 LIS 演算法解決。
第二題
第二題寫的是給一個數字 n，要用最少個 Fibonacci 數列中的數字組成，輸出那些數字。應該算是數論的題目吧？！基本上就是從小於 n 的數開始找，一直減下去減到 0。
第三題
第三題寫的好像是判斷點在多邊形內還多邊形外吧，算是普通的計算幾何題目。
第四題
第四題就寫 Problem D，然後無限 Wrong Answer。
第五題
第五題寫的是給兩個方程式，就找出這兩個方程式的兩個共同質數解。就把兩個式子劃上等號，經過移項後，在解這新的方程式即可。
第六題
第六題寫得是圖論題目，就按照要求把兩兩不互質的數字連上一條邊構成一張圖。再找出這張圖 cut vertex 的數量。
第七題
第七題寫得是給一個式子 y ≡ ax + b mod m，找出 inverse (c,d) 使得 x ≡ cy + d mod m。又是一題數論題…。
其他只能放棄了。