競技プログラミングにおける2-SAT問題まとめ

2-SATとは

• 「x ∧ y」の選言の充足判定をする 解説 コドフォ記事
• 2-SATはSCCで解ける
• ダメな組合せが見つかったときに制約を作る

問題

• yukicoder No.274 The Wall 解説
• CF400 The Door Problem
• yukicoder No.470 Inverse S+T 解説1 解説2
• CC Vertex Cover 解説
• CF403 Underground Lab
• CF411 National Property
• SRM 464 Med ColorfulDecoration 解説1 解説2
• ARC069 Flags
• GCJ 2017 Round2 C. Beaming With Joy
• AtCoder 貢物 (2-SATで部分点。満点回答はもっとヤバイらしい) 解説
• (分からない)東京大学プログラミングコンテスト2013 E 2-SAT (2-SATを使う問題じゃないかも。一応乗せておく) 解説
• yukicoder No.1078 I love Matrix Construction