けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2-SAT

AtCoder ABC 210 F - Coprime Solitaire (橙色, 600 点)

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 つも…

2-SAT で密な節を解消する方法

2-SAT 制約条件:2-SAT 密グラフグラフの辺数削減テク:うまく並べて隣接する部分のみに辺を張るテーマ解説記事スラック変数 SAT

結論先に結論から。リテラルに対して、以下の条件 A, B, C は同値である。 A：のうち、True であるのは 1 個以下である B：任意の () に対して、節を充足する C：新たなリテラルの値を適切に定めたとき、以下をすべて充足する 1：節 () 2：節 () 3：節…

AtCoder Library Practice Contest H - Two SAT (2D)

ACLpractice AtCoder 2-SAT 制約条件:2-SAT 強連結成分分解数直線上のN点の問題どれか1つ求める Yes/No判定問題復元論理パズル解空間:O(2^N)通りの選択肢 N個のペア値の問題制約条件:距離K以下の2頂点 SAT NoviSteps2D

2-SAT は強連結成分分解の典型的な応用例！問題へのリンク問題概要旗を数直線上に設置したい。旗は、座標または座標に設置可能である。ただし、どの 2 つの旗も、その距離が以上となるようにする必要がある。本の旗を設置することが可能かどうかを…