推 puzzlez: 推熱血．。 01/01 15:37
→ buffalobill: 1735分路過... 01/05 15:52
這次我自己因為各種原因跳掉了三題，第四題還因為少看一個條件多送一次被扣 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 了，好在簡單分析可以確定答案是七位數
所以搜起來並沒有那麼難就是
--
実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」
亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」
実琴：「難道你沒有男人的尊嚴了嗎?!」
亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」
－－プリンセス・プリンセス 第二話
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1451621510.A.1A2.html