Darsein https://blog.hatena.ne.jp/Darsein/ Darseinのプロコン日記 https://darsein.hatenadiary.org/ 会津合宿Day1のD問題に「与えられた真理値表に対応するBDDを構築し、頂点数を求めよ」という問題が出ました。 想定解法は「二分決定木作って頑張って簡約化」らしいですが、これはBDDを構築しなくても解けます。変数をx1,x2,...,xn、与えられた真理値表を表す文字列をsとします。ここで、sの前半2^(n-1)個はx1を0に固定したとき、後半2^(n-1)個はx1を1に固定したときの真理値表を表していることに注目します。 これをBDD上で考えると、変数がx1のノードで、前半が左の子、後半が右の子に対応する部分BDDを表している、と考えることができます。 ということはまず、前半と後半が一致する… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdarsein.hatenadiary.org%2Fentry%2F20130903%2F1378218639" title="ACPC Day1 D - Darseinのプロコン日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-09-03 23:30:39 rich https://darsein.hatenadiary.org/entry/20130903/1378218639 1.0 100%