今年好不容易把每一題寫好寫滿，滿分完成比賽 題目列表：http://www.puzzleup.com/2015/archive/ 我也來分享一下我的心得 http://www.puzzleup.com/2015/puzzle/?2 我覺得最有趣的是Q2，我是使用 Pólya enumeration theorem https://en.wikipedia.org/wiki/Pólya_enumeration_theorem 定理的描述有一些代數的術語，但其實用起來不會很難 有空的時候我可以再補詳細的說明 另外幫補一下缺的答案 ※ 引述《LPH66 (-6.2598534e+18f)》之銘言： : 這次我自己因為各種原因跳掉了三題，第四題還因為少看一個條件多送一次被扣 20 分 : 所以最終只有 1874 分，連前五十名都沒上 (望 : 以下是我的參考答案: : (86%) 1. 7967/1069335 : (85%) 2. 333 : (82%) 3. 985432107 : (90%) 4. 538171062 : (63%) 5. 60 : (97%) 6. 32 (30%) 7. 24 : (86%) 8. 6021 : (取消)9. 1908 : (92%) 10. 64570081 : (92%) 11. 84 : (92%) 12. 2840 (79%) 13. 117649 : (96%) 14. 19 : (80%) 15. 1436 : (83%) 16. 14 : (91%) 17. 23751 : (67%) 18. 9574083 (90%) 19. 294879 : (84%) 20. 5 : Q9 似乎是題意不清的原因所以取消了 : Q7 跟 Q13 兩題我沒做的原因是因為這兩題問的是一類圖論難題的特例 : Q7 問的是最小支配點集 (這題型 2014 就出過了: 2014 Q10 #1KB5GXpU) : https://en.wikipedia.org/wiki/Dominating_set http://www.puzzleup.com/2015/puzzle/?7 第7題我也覺得非常難，是靠Google大神的 http://mathoverflow.net/questions/210358/four-dimensional-rook-domination : Q13 問的是最大獨立點集 : https://en.wikipedia.org/wiki/Independent_set_(graph_theory) : 之所以是難題的原因是一般來說他們都是 NP 完全 (意思是連用程式都沒有捷徑) : (關於 NP 完全的簡介可以去找看數學版這篇講踩地雷的我的文章: #1GPBcQPe (Math) ) : 雖然這兩題的圖都是特別型式的圖，不過 (ry http://www.puzzleup.com/2015/puzzle/?13 第13題倒是可以自己推出答案 7^6 ，以下是證明 因為合乎題目條件的集合中，任兩個元素的前6位都不能完全相同 (否則最多只差1位) 而前6位就只有7^6個組合，所以不可能有超過 7^6 個元素 接著要構造一個大小7^6且滿足原題條件的集合 令A=0,B=1,C=2,D=3,E=4,F=5,G=6 任何一個7-letter code都可以對應到一個值，就是每一位對應的數相加 例如GFEDCBA就是6+5+4+3+2+1+0=21 我們取所有相加是7的倍數的code成一個集合，這個集合大小正是7^6且任兩元素不相似 首先，因為前6位亂取有7^6種組合 根據除7的餘數，第7位總可以補一個讓它總和是7的倍數，所以有7^6個 再來，任兩元素都不會只差1位 因為在其他6位相同，只有1位不同的情況下，不可能他們總和餘7會相同 故得證 : Q19 單純只是繁題，那陣子又比較忙所以沒時間寫程式 (死) : 其他的難題: Q5 我後來找到了了巨人的肩膀站 XD : https://en.wikipedia.org/wiki/Crossing_number_%28graph_theory%29 : 如維基百科所說，現有的理論對這題要問的東西在完全圖上只有到 K12 有確定 : 其他都是上界；而這題問的是 K10 所以就直接代結論了 XD http://www.puzzleup.com/2015/puzzle/?5 Q5我也是Google XD : Q18: 這題最後還是 Programup 了，好在簡單分析可以確定答案是七位數 : 所以搜起來並沒有那麼難就是 http://www.puzzleup.com/2015/puzzle/?18 這次有滿多題都是Programup，有點可惜 Q18在改題目前我有手算出答案(原本是any "two" adjacent digits) 改成3位我就不會了，又只好寫程式XD 而且以現今CPU的速度，就算不做任何分析，完全暴搜10!的排列也只是秒殺 其他有幾題至少還需要例如DP的技巧 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 206.71.243.2 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/puzzle/M.1451665944.A.114.html