第二屆高一程式設計排名賽題目資料與賽後分析

Sylveon · 發表於 2014-6-7 22:17:18

第二屆高一程式設計排名賽

出題者 LFsWang & allenwhale

時間：2014/06/07

[youtube]DmxcgE5HEy4[/youtube]!?

最終結果：TOJ

註冊帳號困難請寄件至forum.tfcis.adm@gmail.com請管理員協助
題目資料：(MEGA) https://mega.co.nz/#F!wl8EGBqA!lkBSnBQ-_e042tlkEi-6lg
檔案格式：TAR.XZ (一般壓縮軟體即可解壓縮)
解題報告：(GDOC)
[GOOGLEPTT]0Bzxow2VOUeFGS2FNV0VWOEFrV00[/GOOGLEPTT]

總結：今天大家都很努力了，我覺得敢來挑戰就是一個不錯的開始，看完大家的code，可以發見通常code較整齊的人答題上會較順暢。這次題目設計是以多個面向，以測資分配來評斷選手的實力，根據不同的能力，來拿到多少分數，今日前10名的走勢圖還滿激烈的，多或少一筆測資都可能與獎金無緣，希望大家喜歡這一次的出題風格與編排，以下我就根據大家的答題狀況做個說明。

逐題分析：
A.伊布的邀請

最高得分：100 (蘇多門 00:09:12)
上傳次數：140次
難度：易 ★
考點：基本運算處理。
分數散布：

分數	人數
100	10
40	5
30	3
10	1
0	7

大致上看完大家的code，會WA大至兩種原因：

複數運錯誤
格式輸出錯誤

複數運算國中生可能比較不公平，不過他仍然有AC，通常是乘除打錯，或是不知道除法要用共扼複數通分之類的，不過這可是高一的數學，忘的也太快了吧！
格式輸出錯誤方面，我想我的範例測資已經明顯提示正負號的問題了，但是仍有許多人沒注意到負號的問題，真的很可惜。至於CE，那種東西在你電腦就CE了，不用想judge上一定也CE，這種code就不用傳了，浪費上傳時間。

B.害羞的火精靈

最高得分：60 (楊承諭 00:09:12)
上傳次數：67次
難度：困難 ★ ★ ★ ★ ★
考點：乘法反元素(逆元)之應用。
分數散布：

分數	人數
60	1
30	10
0	11

基本上這題需要較多的數學知識，在程式設計競賽，取模是常見的操作，要能掌握模運算是件重要的是。我研究大家的Code，大致分兩類做法，一為巴斯卡定理做DP，或是用階乘運算，其實兩者若處理好，DP有壓縮，或是階乘用模擬約分的方法，前80%的分數其實很容易的，最後的20分，才是給大家引入了MOD的概念，給大家研究，Cn取m的題目很多，但像這題一樣機車的很少，請大家要仔細地思索當中的奧妙。

C.葉精靈的果實

最高得分：90 (涂家銘 01:11:11)
上傳次數：30次
難度：困難 ★ ★ ★ ★ ★
考點：DP。
分數散布：

分數	人數
90	1
50	4
0	6

這題個人評價：根本亂寫一通！除了楊承諭同學的方法接近正解了，其餘0分方法幾乎沒有抓到題目要求，背包問題是個經典題目，基本上前80的分數是3星等級，90分算是4星，100分需要較為多的知識推理，但是相對於第二題來說是較容易的，背包是DP題的基礎型，請同學不要以為我會100分的做法就好，應該要把每一個level的解法詳加閱讀，來增進自己的實力！

D.水精靈的舞蹈

最高得分：90(駱佳駿 01:11:55)
上傳次數：53次
難度：基本 ★ ★ ★
考點：三分搜尋法
分數散布：

分數	人數
90	1
30	1
0	10

這其實算是基礎的裸三分搜，這種題目來滿少單獨出的。基本上只要會三分搜，就能輕易解決！不過呢這題有50%的分數N=2，答案就是(A+B)/2，隱藏版送分，只是這一題大家比較晚寫，等到開始有人發見這件事實，已經到了黑暗時期，無法讓大家跟題。三分搜是個簡單的技巧，經常用在單調凸/凹函數上，像今年TOI 1模就有該題型，三分搜是個你我必備的工具！

E.太陽精靈的項練

最高得分：70(涂家銘 01:17:37)
上傳次數：40次
難度：基本 ★ ★ ★
考點：KMP failure function (DP)。
分數散布：

分數	人數
70	2
50	5
0	10

這議題我覺得大家寫的不夠理想，只要做因數列舉，加個簡單的字串比對就有基本分，這題的input很大，大概一筆最多50MB，對於使用較慢的IO函數會有點吃虧。KMP演算法是當今具最佳效率的字串匹配演算法，但受限於硬體設計，其實並無法顯現KMP的優勢，而failure function的運作方法，巧妙的運用已知資訊，與Z value有異曲同空之妙，不少字串題與者兩個的求職有很大關聯，如最長回文等等，值得大家深思。

F.與冰精靈健行(Special Judge)

最高得分：40(涂家銘 01:17:37)
上傳次數：29次
難度：基本 ★ ★ ★ ★
考點：隨機化策略。
分數散布：

分數	人數
40	5
20	2
0	1

大家都目測地圖拉，其實認真要亂搞，可以發現第5筆測資的誤差範圍超大，隨便估計下，亂猜一下子就能矇到了。來說說正常的吧，有經驗的看到這一題是TSP(Travelling salesman problem)問題，TSP是NP-hard，基本上解法時間複雜度都在O(2[sup]n[/sup])以上，但是這題最大的N達到了100，顯然的就是隨機化的信號！TSP除了隨機化求近似解外，還有基於平面圖近似解演算法，這裡選用的方法為爬山演算法，剛方法大致分兩部分，一是隨機行走找最優方向，二是在遇到局部最佳解時的隨機重啟策略，該方法可以輕鬆騙過許多奇怪的題目，大家不仿試試看吧！

G.雷精靈的煩惱(互動題)

最高得分：0(Nobody 00:00:00)
上傳次數：15次
難度：基本 ★ ★
考點：隨機化策略。
分數散布：

分數	人數

0	2

其實這題還滿簡單的，可能大家對這種互動題沒什麼接觸，不敢寫下這一題吧！其實只要能想到一套找球的流程，穩定的寫出來，不要犯語法錯誤，應該是能輕易答題的，當然你可以寫一個具相同功能的函數來輔助自己，回家練習不仿試一試！

H.月精靈的祝福

最高得分：100(駱佳駿 00:08:40)
上傳次數：108次
難度：基本 ★
考點：基本IO。
分數散布：

分數	人數

100	24
60	2
0	3

送分題啊！知道我出題風格的先看最後一題通常會有不錯的收穫！沒答對這一題的請再多練習吧！這已經比我的hello world簡單太多了XD

標準程式：

購買主題 已有 1 人購買 本主題需向作者支付 30 枚金幣 才能瀏覽

John · 發表於 2014-6-7 23:10:05

謝謝提供資料！

感覺很多東西該寫出來沒有寫出來啊...

另外，C D兩題的考點貌似擺反了這樣？

[競賽分享] 第二屆高一程式設計排名賽題目資料與賽後分析

台南一中資訊社

新手達陣

程式設計達人 - 2014

[競賽分享] 第二屆高一程式設計排名賽 題目資料與賽後分析

台南一中資訊社

新手達陣

程式設計達人 - 2014

[競賽分享] 第二屆高一程式設計排名賽題目資料與賽後分析