※ 引述《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
跑起來若超過時間, 應該也在 time limit 的幾倍之內
最佳化 D 似乎比較有希望
orz 要不要分享一下你們寫這題的經驗?
(三隊解出 D 的隊伍, 有兩個隊名叫 orz ...)
回到 F, 我試了一下, branch&bound 用一些 heuristic 估計 upper bound
大約可以解到 n=30 (random input 幾乎大部份都瞬間跑完, 少數要花個幾秒)
--
"靈感 = 經驗 + 嘗試 + 快速的計算能力"
--- Ledia
"靈感, 是實力的累積"
--- untitled
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.70.142.187