計算量が本質的に改善する枝刈り
めちゃくちゃ面白い!!! 問題へのリンク 問題概要 (意訳) 思いを寄せている先輩に 週後に告白したいので、その日までに先輩の好感度を最大化しておきたいです。最初、「所持金」と「好感度」はともに 0 です。毎週、以下のいずれかの行動を起こすことがで…
AOJ
JAG
3-SAT
SAT
ランダムウォーク
操作
全探索
応用的な探索
スイッチ
盤面を予め変更する
復元
二次元グリッド
枝刈り
パズル
計算量が本質的に改善する枝刈り
JAG模擬地区
AOJ-ICPC
AOJ-ICPC900点
指数探索系問題
マルチテストケース問題
(定数)×Nのグリッド
枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…