※ 引述《smartboy (小光光)》之銘言：
: ※ 引述《ledia (contemplation)》之銘言：
: : F 的 strong king 題則是預期用夠好的順序來窮舉 tournament 所有可能組合
: : 大部份簡單的 heuristic 都會有反例, 測資有為不讓 heuristic 解法答對設計過
: : 但是出題教授說在出了題目之後他的學生把 close form 解出來了
: : 這跟我看到這個題目的第一感其實是蠻符合的
: : 只是我求不出 close form (我承認... 我無能... :~)
: 若不論 close form 的話,
: 這類需要 heuristic 或 cut 的 search 題目在這幾年的比賽滿少出現的
: 這類題目對選手也是個考驗 -- 在時間有限的情況下, 該先做其他題,
: 還是要想不一定有效的 cut... 說不定花時間寫 search 其實存在好演算法可解
: 若是我, 相較之下, 我大概會先寫 D 吧, 感覺起來 2*16!/4!/4!/8!=1.8M node
問個問題喔,為什麼是2*16!/4!/4!/8!
C(16,4)*C(12,4) = (16!/4!/12!) * (12!/4!/8!) = 16!/4!/4!/8!
是我忽略了什麼嗎?
: 跑起來若超過時間, 應該也在 time limit 的幾倍之內
: 最佳化 D 似乎比較有希望
: orz 要不要分享一下你們寫這題的經驗?
: (三隊解出 D 的隊伍, 有兩個隊名叫 orz ...)
: 回到 F, 我試了一下, branch&bound 用一些 heuristic 估計 upper bound
: 大約可以解到 n=30 (random input 幾乎大部份都瞬間跑完, 少數要花個幾秒)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.250.175