問題 yukicoder.me 2-SATについての前提 2-SAT問題の解き方 論理和を論理包含に変換 1を元にimplication graphを作る 2のimplication graphを強連結成分分解する 3の結果、ある要素Xとその否定￢Xが強連結成分であるなら、その2-SATを満たす解は存在しない …

前提 有向グラフGの頂点の部分集合をSとする。 Sが強連結であるとは、Sの任意の2頂点間が行き来可能であること Sが強連結成分であるとは、Sに他のどの頂点を追加してもそれ以上強連結にならないこと 強連結成分分解とは、強連結成分を1つの頂点にまとめるこ…

AC Libraryに、より高速なライブラリが存在する。 https://atcoder.github.io/ac-library/document_ja/string.html 以下に載せた実装は、自分の理解を深めるために実装したもの。（蟻本のものにアレンジを加えclass化した。計算量は変わらず、Manber & Myers…

制約から座標圧縮をすべきであることは想像しやすいが、この問題はかなり難しいと思った。 atcoder.jp 前提 座標圧縮 pione.hatenablog.com 解説 座標圧縮を行う問題でよく見かけるパターンは以下の2つである。 いくつかの長方形が与えられて、長方形が重な…

前提 一次元座標圧縮はBITによる転倒数の数え上げでお馴染み。 二次元の場合は、x軸、y軸を独立に捉えることでほぼ同様に求めることができる。 二次元座標圧縮における注意点は、登場する座標の1つ隣の座標も登録する点にある。これは登場する座標だけで圧縮…