Puzzleup 2015 成績出爐 - 拼圖

今年好不容易把每一題寫好寫滿，滿分完成比賽
題目列表：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的技巧

--