今年好不容易把每一题写好写满，满分完成比赛
题目列表：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的技巧