マトロイドの凸構造 - けんちょんの競プロ精進記録
この記事は、Competitive Programming Advent Calendar Div2012の12日目の記事として書きました。 0. はじめに 今回はマトロイドについて書きたいと思います。 マトロイドはGreedyとの関連でよく耳にします。では、そもそもマトロイドがGreedy性を持つのは何故でしょうか？実は、マトロイドは単に「Greedyの一例」として出て来るばかりでなく、「現在効率的なアルゴリズムが知られている問題の殆どはマトロイドが何かしら関わっている」と言える程にイイ構造を持っています。以前、以下のようなツイートをしました。 dpやってていつも思うのが、なんか凸凹してるなーと。凸凹し過ぎてdpじゃなきゃ解けないよな、みたいな感じ。マトロイドは凹んでるところがない凸なイメージ。だから、局所最適狙う貪欲法だけで最適解に辿り着ける。焼き鈍しなんて必要ない。 本記事では、この
Rubyで学ぶオブジェクト指向／デザインパターン
Rubyで学ぶオブジェクト指向入門 オブジェクト指向プログラミング入門（その１).pdf オブジェクト指向プログラミング入門（その２).pdf オブジェクト指向プログラミング入門（その３).pdf オブジェクト指向プログラミング入門（その４).pdf 添付１ 論理シミュレータクラス図.pdf 添付２ Pque説明.pdf 添付３ 回路シミュレーション例.pdf 添付４ LogicSimソースコード オブジェクト指向プログラミング入門（その５)簡易システム性能評価シミュレータ.pdf オブジェクト指向プログラミング入門（その６)RUnitに適用されたデザインパターン.pdf Rubyで学ぶデザインパターン パターンサンプルコード このサンプルコードは、Java言語で学ぶデザインパターン入門 結城 浩（著） （ソフトバンクパブリッシング ISBN:479731462）に掲載されているサンプルソ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
