Puzzleup 2015 成績出爐 - 拼圖

這次我自己因為各種原因跳掉了三題，第四題還因為少看一個條件多送一次被扣 20 分

所以最終只有 1874 分，連前五十名都沒上 (望

以下是我的參考答案:

(86%) 1. 7967/1069335
(85%) 2. 333
(82%) 3. 985432107
(90%) 4. 538171062
(63%) 5. 60
(97%) 6. 32
(30%) 7.
(86%) 8. 6021
(取消)9. 1908
(92%) 10. 64570081
(92%) 11. 84
(92%) 12. 2840
(79%) 13.
(96%) 14. 19
(80%) 15. 1436
(83%) 16. 14
(91%) 17. 23751
(67%) 18. 9574083
(90%) 19.
(84%) 20. 5

Q9 似乎是題意不清的原因所以取消了

Q7 跟 Q13 兩題我沒做的原因是因為這兩題問的是一類圖論難題的特例

Q7 問的是最小支配點集 (這題型 2014 就出過了: 2014 Q10 #1KB5GXpU)

https://en.wikipedia.org/wiki/Dominating_set

Q13 問的是最大獨立點集

https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

之所以是難題的原因是一般來說他們都是 NP 完全 (意思是連用程式都沒有捷徑)

(關於 NP 完全的簡介可以去找看數學版這篇講踩地雷的我的文章: #1GPBcQPe (Math) )

雖然這兩題的圖都是特別型式的圖，不過 (ry

Q19 單純只是繁題，那陣子又比較忙所以沒時間寫程式 (死)

其他的難題: Q5 我後來找到了了巨人的肩膀站 XD

https://en.wikipedia.org/wiki/Crossing_number_%28graph_theory%29

如維基百科所說，現有的理論對這題要問的東西在完全圖上只有到 K12 有確定

其他都是上界；而這題問的是 K10 所以就直接代結論了 XD

Q18: 這題最後還是 Programup 了，好在簡單分析可以確定答案是七位數

所以搜起來並沒有那麼難就是

--
実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」
亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」
実琴：「難道你沒有男人的尊嚴了嗎?!」
亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」
－－プリンセス・プリンセス 第二話

--