スラック変数
AtCoder
AtCoder600点
ABC-F
橙色diff
2-SAT
制約:数値が10^6以下
密グラフ
グラフの辺数削減テク:スーパー頂点を用いてsparseに
グラフの辺数を削減する
2-SATの密を解消する累積OR
スラック変数
N個のペア値の問題
解空間:O(2^N)通りの選択肢
カードや山札を扱う問題
数学(整数問題)
見積り大事
Yes/No判定問題
互いに素
各素因数ごとに考える
そのまま覚えたいシンプル設定の中堅以上の典型問題
f(i,j)をiとjとに分離する
線形性に着目する
SAT
グラフテク:スーパー頂点
2-SAT の「密」を解消する累積 OR テクを学んだ！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。 上手く選択することで、上を向いている数値がどの 2 つも…
結論 先に結論から。 リテラル に対して、以下の条件 A, B, C は同値である。 A： のうち、True であるのは 1 個以下である B：任意の () に対して、節 を充足する C：新たなリテラル の値を適切に定めたとき、以下をすべて充足する 1：節 () 2：節 () 3：節…
