ACLPC H
ACLPC_H
Two-SATは二つの項のORをANDで繋いだ形の論理式の解を求める問題
でも問題Hの場合、Two-SATにするよりその原理を使ってグラフを直接構築する方がわかりやすいと思う
Two-SATを強連結成分分解に帰着する原理
AならばBって関係は有向グラフの辺だと考えられる
このグラフの強連結成分を考えると、どれか一つでもTrueなら全部がTrueになるので、全部Trueか、全部Falseかのどちらかである
(A \vee B) = (\neg A \Rightarrow B) \wedge (\neg B \Rightarrow A)によってORは「ならば」に変換できる
なのでグラフを構築して強連結成分分解し、成分ごとに真偽値を割り当てていけば解が得られる
Aとnot Aが同じ成分に入ってたら充足不可能、違う成分ならAが先の時にTrueとすれば良い
この割当で問題が起きないことをきちんと示せてない。一般のグラフではダメな気がする。
具体的な問題Hに戻ると「Xiに旗を置いたなら、距離D未満の位置に旗を置いてはいけない」の「ならば」を辺とするグラフを構築して強連結成分分解すればよい
Related Pages
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×UnionFind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×UnionFind×mod_pでの組み合わせ×educational_dp_contest×動的計画法×AtCoder Library Practice Contest×AtCoder Library×帰着する力×帰着訓練→
- →atcoder×AtCoder Library Practice Contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×UnionFind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]