ACLPC H

強連結成分分解を使うことでTwo-SATが解ける 2-SAT
Two-SATは二つの項のORをANDで繋いだ形の論理式の解を求める問題
- でも問題Hの場合、Two-SATにするよりその原理を使ってグラフを直接構築する方がわかりやすいと思う
Two-SATを強連結成分分解に帰着する原理
- AならばBって関係は有向グラフの辺だと考えられる
- このグラフの強連結成分を考えると、どれか一つでもTrueなら全部がTrueになるので、全部Trueか、全部Falseかのどちらかである
- $(A \lor B) = (\neg A \Rightarrow B) \land (\neg B \Rightarrow A)$ によってORは「ならば」に変換できる
- なのでグラフを構築して強連結成分分解し、成分ごとに真偽値を割り当てていけば解が得られる
  - Aとnot Aが同じ成分に入ってたら充足不可能、違う成分ならAが先の時にTrueとすれば良い
    - この割当で問題が起きないことをきちんと示せてない。一般のグラフではダメな気がする。
具体的な問題Hに戻ると「Xiに旗を置いたなら、距離D未満の位置に旗を置いてはいけない」の「ならば」を辺とするグラフを構築して強連結成分分解すればよい

🪴 Quartz 4.0