※ 引述《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