おねえさんを組み合わせ爆発から救う：無駄を省いてBDDを作る - きしだのHatena
おねえさんを組み合わせ爆発から救うために、経路を二分決定木として表しました。 http://d.hatena.ne.jp/nowokay/20121016#1350351212 前回の二分決定木を見ると、「1:2」「1:3」を通るとした場合、あとはどのような選択をしても単純な経路にならず「F」にたどりつきます。同様に、両方通らない場合も「F」になります。 このように、それ以降はどのような選択をしても結果がひとつに決まるという場合、それ以降のツリーを省略すると、決定木がすっきりします。 また、それ以降の分岐が等しくなる場合をまとめることもできます。そうすると、単純な二分決定木ではとても画面におさまりきらなかった2x2マスの経路も表示できるようになります。 このような図はツリーではなくなっているので、二分決定図、BDD(Binary Decision Diagram)といいます。この図では、「
おねえさんのコンピュータ
同じ所を２度通らない道順の数 Total number of routes that do not pass by the same place twice
第二版が出ます！プログラミングコンテストチャレンジブック - iwiwiの日記
一昨年 9 月に初版が出て以来「蟻本」の愛称で皆様にご好評頂いていた僕と岩田 (id:wata_orz) と北川の「プログラミングコンテストチャレンジブック」ですが，お陰様で，このたび第二版が出版されます！第二版の発売日は 1/27 の予定です．よろしくお願いします． （初版の紹介記事はこちら） 改訂による追加部分は，以下になります． 4 つの新しいトピック：計算幾何，枝刈り探索，分割統治法，文字列アルゴリズム 練習問題コーナー 発展内容コーナー ページは 50 ページ増となっています． 練習問題コーナー 練習問題コーナーでは，本書で取り上げた各トピックに関連したオンラインジャッジ上の問題を紹介しています．例題を理解するだけでなく，実際に練習問題を自分で解くことで，一層の定着や応用力の増強を図ることができます． 発展内容コーナー 発展内容コーナーでは，難易度や本の性質の都合等で本書で紹介し
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
