piroz95 https://blog.hatena.ne.jp/piroz95/ ぴろずメモ https://piroz.hatenablog.com/ 問題解説 2-SATを想定解とする問題をyukicoderで出題しました。 No.470 Inverse S+T Problem - yukicoder想定解通りの2-SAT解法とは別に、計算量のよく分からない探索を結構通されてしまいました。 探索解の中に正当なものがあるのか、調べていたところ2-SATを暗黙的に解いている提出が見つかりました。 たとえばヘクトさんの提出です。その解き方というのが、Wikipediaの2-SATの解法の一つとして載っているLimited backtrakingです。 2-satisfiability - Wikipedia http://epubs.siam.org/do… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpiroz.hatenablog.com%2Fentry%2F2016%2F12%2F21%2F210218" title="2-SATを探索で解く方法とyukicoder No.470 Inverse S+T Problem - ぴろずメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=%20%28%5Clnot%20x_1%20%5Clor%20x_2%29%20%5Cland%20%28%5Clnot%20x_1%20%5Clor%20%5Clnot%20x_2%29%20%5Cland%20%28%5Clnot%20x_1%20%5Clor%20x_5%29%20%5Cland%20%28x_1%20%5Clor%20x_3%29%20%5Cland%20%28%5Clnot%20x_3%20%5Clor%20x_4%29%20%5Cland%20%28x_5%20%5Clor%20x_6%29 Hatena Blog https://hatena.blog 2016-12-21 21:02:18 rich https://piroz.hatenablog.com/entry/2016/12/21/210218 1.0 100%