2017-09-12から1日間の記事一覧

赤黒木

最初に これいる?要はmergeとかsplitとかできるようになった強い配列です。ここらへんを参考にして実装しました。 https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf http://algoogle.hadrori.jp/algorithm/prbtree.html h…

2-SAT

(P||Q||...)&(R||S||...)みたいな連言標準形で書かれた論理式を真にする割り当てはあるかを判定する問題をSATといいます。 2-SATの場合カッコ内のリテラル数が高々2つ、つまり(P||Q)&(R||S)みたいになってます。2-SATの解き方は蟻本の通り、SCCを使って真のn…