スイッチ
AOJ
JAG
3-SAT
SAT
ランダムウォーク
操作
全探索
応用的な探索
スイッチ
操作:盤面を予め変更する
復元
グリッド
枝刈り
パズル
計算量が本質的に改善する枝刈り
JAG模擬地区
AOJ-ICPC
AOJ-ICPC900点
指数探索系問題
枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…
AtCoder
AtCoder300点
ABC-C
連立一次方程式
0と1の問題
bit全探索
全探索
方程式
パリティ
Gauss-Jordanの掃き出し法
スイッチ
緑色diff
指数探索系問題
再帰関数を用いた全探索
bit 全探索 問題へのリンク 問題概要 個のスイッチがある。スイッチによって 個の電球が点いたり消えたりする。 電球 は 個のスイッチに繋がっており、スイッチ のうち on になっているスイッチの個数を 2 で割った余りが に等しい時に点灯します。 全ての電…