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

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

2023-08-04から1日間の記事一覧

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

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