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

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

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 つの旗も、その距離が 以上となるようにする必要がある。 本の旗を設置することが可能かどうかを…

JOI 二次予選 2021 E - スパイ 2 (難易度 10)

面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…

AOJ 2574 Magical Switches (JAG 模擬地区 2013 J) (900 点)

枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…