読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

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

2-SATとは

しっかりした定義ではなく競技プログラミングで使う定義では、「x ∧ y」の選言の充足判定をすること。
http://naoyat.hatenablog.jp/entry/2013/07/13/220034
http://codeforces.com/blog/entry/16205
この辺りが詳しい。
2-SATを特にはSCCを使うと解けるらしいけれど、あんまり理解していない。

どういう問題で使えるのか
  • n個のものについて2つの状態のうち1つを選択する。つまり、ありうる可能性が2^n通りある
  • n <= 2000
  • 制約が作れる
  1. ダメな組合せが見つかったときに制約を作る
  2. http://naoyat.hatenablog.jp/entry/2013/07/13/220034の一節『「x と y が共存できない」¬(x ∧ y) が ¬x ∨ ¬y に等しいことを利用』が全て

問題(下に向けて発展的になる)

yukicoder No.274 The Wall

http://yukicoder.me/problems/no/274
貪欲解もあるが、2-SATの入門問題として最適。
解説
http://mmxsrup.hatenablog.com/entry/2016/12/23/151256

Codeforces Round #400 (Div. 1 + Div. 2, combined) D. The Door Problem

http://codeforces.com/contest/776/problem/D
2-SATの入門編のような問題

Codeforces Round #403 Div2 E. Underground Lab

http://codeforces.com/contest/782/problem/E
2つの状態のうち1つを選択する -> SAT使えそう
問題文を読む方が難しい

ARC 069 F. Flags

http://arc069.contest.atcoder.jp/tasks/arc069_d
このまとめのきっかけ。解けてない。

技術室奥プログラミングコンテスト#2 G 貢物

http://tkppc2.contest.atcoder.jp/tasks/tkppc2016_g
2-SATで普通に解くと部分点。満点回答は以下の解説。
さっぱり分からん上、antaさんしか満点回答出してない。
解説
http://www.slideshare.net/maroonrk/ss-64770360

(分からない)東京大学プログラミングコンテスト2013 E 2-SAT

http://utpc2013.contest.atcoder.jp/tasks/utpc2013_05
2-SATを使う問題じゃないかも。一応乗せておく。
解説
http://kmjp.hatenablog.jp/entry/2014/04/04/0930