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

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

2-SAT

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

2-SAT の「密」を解消する累積 OR テクを学んだ! 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。 上手く選択することで、上を向いている数値がどの 2 つも…

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

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

AtCoder Library Practice Contest H - Two SAT

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