典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ - Qiita
はじめに --- DP は役に立つ はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 巷ではよく「DP なんて実務では使わない」といった言説が定期的に流れますが、そんなことはないです。僕自身この 2 年間で DP が使える実務案件に 3 件くらい関わりました！ それはともかくとして、DP を学び立ての方がよく抱く悩みとして「バリエーションが多すぎて混乱するし、統一的なフレームワークがほしい」というのがあります。確かに DP のバリエーションは非常に多岐にわたるのですが、そのほとんどが以下の 3 つのフレームワークで説明できると思います: ナップサック DP 区間 DP bit DP 今回はこのうちのナップサック DP について、とにかく
マトロイドの凸構造 - けんちょんの競プロ精進記録
この記事は、Competitive Programming Advent Calendar Div2012の12日目の記事として書きました。 0. はじめに 今回はマトロイドについて書きたいと思います。 マトロイドはGreedyとの関連でよく耳にします。では、そもそもマトロイドがGreedy性を持つのは何故でしょうか？実は、マトロイドは単に「Greedyの一例」として出て来るばかりでなく、「現在効率的なアルゴリズムが知られている問題の殆どはマトロイドが何かしら関わっている」と言える程にイイ構造を持っています。以前、以下のようなツイートをしました。 dpやってていつも思うのが、なんか凸凹してるなーと。凸凹し過ぎてdpじゃなきゃ解けないよな、みたいな感じ。マトロイドは凹んでるところがない凸なイメージ。だから、局所最適狙う貪欲法だけで最適解に辿り着ける。焼き鈍しなんて必要ない。 本記事では、この
The Secret Number 解説
問題名：The Secret Number (PKU) 出典：Problem C, ACM/ICPC Japan Domestic, 2003-10-03 難易度：☆☆☆ 問題の種類：DP 解法：動的計画法 解答ソースコード： 2030-deq_loop.cpp（ループ） 2030-deq_memo.cpp（メモ化探索） アルゴリズムの概略と計算量 素直な方法 「2次元のマトリックスから最も大きな数字列を探し出せ」という問題。 真っ先に思い浮かぶのは「始点ノードを探して再帰で右or下に数字を連結していく」という解法でしょう。 先頭のゼロや細かなあれこれを無視すると，こういう感じのコーディングになります： def rec(x, y, string): string += field[x][y] answer = max(answer, string) if 右が数字: rec(x+1, y,
指数時間アルゴリズム入門
2. 自己紹介 TopCoder: ◎wata TCO2010Marathon優勝など Twitter: @wata_orz 東京大学情報理工学系研究科コンピュータ科学専攻 理論計算機科学 (アルゴリズムの理論的な解析とか) プログラミングコンテスト チャレンジブック 2 3. 本日の内容 NP困難問題を解くためのアルゴリズムを扱います 𝑂𝑃𝑇 𝐼 ≤ 𝐴 𝐼 ≤ 𝑐𝑂𝑃𝑇(𝐼) 近似アルゴリズム ヒューリスティック 𝑓 𝑘 𝑝 𝑛 FPT アルゴリズム max 𝑐𝑥|𝐴𝑥 ≤ 𝑏, 𝑥: 整数} { 𝑂∗ 𝑐 𝑛 整数計画 厳密指数時間アルゴリズム 3 4. 効率的な指数時間アルゴリズム 何の指数？ 頂点数? 辺の数? それとも… • 2 𝐸 のアルゴリズムはまず役に立たないが，2 𝑉 のアル ゴリズムならコンテストでもよ
d.y.d. 再帰関数の意味とは不動点である！
02:12 05/09/03 反応リンク集 fixの話 … Perl版、 Perl版、 C++版、 C++版、 Scheme版、 Concurrent Clean版。 （9/4追記: Ruby版、 Erlang版、 Squeak版、 D版。 Sukuna版。 Erlangのprocessを使ったメモ化の例は見てみたいかも。）。 で、 メモ化の話 … Python版、 Python版 （9/4追記: ET版、 Erlang版、 Java版、 PostScript版。 ）。 decoratorは流石かっこいいですね。C++版は…うーん、個人的には、このくらいなら Boost に頼らないで直球ストレートで書いてあげたいところです。 彼はやればできる子なんです。 template<int (*G)(int(*)(int),int)> int fix(int x) { return G( fix<G
DPとかメモ化再帰とか - komiyamの日記
以下の内容は間違いを含んでる可能性が高い。 状態数が少ない問題ではDPやメモ化再帰による解法が結構あるけど、少し整理してみよう。 まず、大前提としてDPやメモ化再帰が使える必要条件はDAGになっていることだろう。ここで考えているグラフは、各状態を頂点、状態遷移を有向辺としたグラフである。確率とかの問題だと辺に遷移確率の重みがつくと考えれば良い。 特に、最小値を求める系の問題では必要十分と言ってもいいかもしれない(何か三角不等式っぽいのが成り立っていればいいような気がする。でも組み合わせの数を求める系だと上手く行かないのでやっぱり嘘か？)。 DPというのは、DAGに対してトポロジカル順序の小さい順に値を決定していくことに他ならない。 メモ化再帰というのは、もらうDPの特殊形式で余計な所を評価しないlazyなアルゴリズムと言えるかもしれない。 こうして書いてみると、DPの欠点が明らかになる。そ
DPの話 (追記) - aizuzia
前回の記事に対してみやむーさんから素晴らしい反響を頂いたので、こちらにレスポンスする形で追記してみます。 そもそも前回の「DPの話」は、こちらのエントリと内容が全く同じなのでした。全然気付いてなくてごめんなさい・・・。 ループのメリットとメモ再帰のメリット 「メモ再帰のメリットは計算が遅延的に行われること」とのことでした。メモ再帰では、「最終的に求めたい状態には絶対に遷移し得ないノード」への計算は行われません。そのようなノードが数多くある問題では、メモ再帰が速くなりうる。なるほど。 似たようなことがループでは絶対できないというわけではありません。配るDPにおいて、配る元のノードの値が初期値 (最短経路だったら inf とか、経路数だったら 0 とか) のままだったら、配っても意味が無いのでやめる。このような枝刈りを加えると、「初期状態から絶対遷移しないノードから」の計算は行われません。 が
DPの話 - aizuzia
この記事は Competitive Programming Advent Calendar のために作成されました。 「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない メモ再帰だと書けるけどループだと書けない、またはその逆 とかいう。 この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人と
DPとかメモ化再帰とか(2) - komiyamの日記
Competitive Programming Advent Calendarでtayama0324さんが素晴らしい記事を書いておられました。なので自分もそれに触発されて、以前書いた記事の続きを書いてみました。以下はtayama0324さんの記事を読んでいることを前提に話をします。 DPのメリットとメモ化再帰のメリット 基本的にはtayama0324さんが触れているメリットでつきていると思うんですが、自分は次のようなメリットもあると考えています(本筋から離れるだけなので、tayama0324さんも知っていた上で敢えて書かなかっのだと思います)。 DPのメリット 配列の再利用でメモリが節約できることがある。 データ構造を工夫しての高速化が書きやすい。 メモ化再帰のメリット 評価が遅延的に行われる。 ひとつずつ説明します。 配列の再利用 これは非常によく知られていることだと思います。配列ではあ
DPの練習として良さそうなやつ - kyuridenamidaのチラ裏
いろいろなDPがありますが、これもまとめとくと良いと思ったので。僕はDPは得意ではないですが、それでもスキルアップに繋がったなあと感じた問題をピックアップしておきます。 DPかメモ化再帰か――ループの中で色々場合分けとかしなきゃいけなかったり、順序付けしにくかったりするＤＰは出来るならメモ化したほうがバグ減ったり実装楽だったりします。メモ化再帰は初期化ミスとかが無くて済むので。再帰が深くなりそうだったり、特殊なテクニック(ある区間をまとめて足したりする)とかする場合はやはりDPじゃないとだめですが、大体はメモ化再帰で代用が効きます。ではDP問の紹介。 (ネタバレ注意) 簡単な数え上げタイプ・Kannondou[☆]・A First Grader[★] 最長増加部分列タイプ( O(n log n)解法が存在するのでググったり蟻本とかを読むと良い。 )・ビルの飾りつけ(2007年度JOI春合宿
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
プログラミングコンテストでの動的計画法
KMCの例会講座で用いたスライドを一部編集したものです。 ビット演算を組み合わせたトリッキーな方法で様々な操作を高速に行う方法を紹介します。
Hawk's Laboratory ≫ JavaScriptによるUI開発におけるStateパターンの利用（3）
このドメインを購入する。 hawklab.jp 2019 Copyright. All Rights Reserved. The Sponsored Listings displayed above are served automatically by a third party. Neither the service provider nor the domain owner maintain any relationship with the advertisers. In case of trademark issues please contact the domain owner directly (contact information can be found in whois). Privacy Policy
Collection & Copy - Deferred、遅延リソースのインターフェース、パターン
JavaScript setTimeoutで実行される関数の中で発生するエラーは、セットした部分のtry/catchで補足することはできません。 function throwError(){ throw new Error('ERROR'); } try{ setTimeout(throwError, 3000); } catch(e){ // ここには到達しない alert(e); } MochiKit.Async.Deferredを使うと、エラーバックでエラーを補足できます。 callLater(3, throwError).addErrback(function(e){ alert(e); }); エラーの補足以外にも、Deferredのインターフェースから以下が行えます。 キャンセル(cancel)状態(fired)コールバックの追加(addCallback)エラーバックの追加
Deferredチェーン、非同期処理の逐次実行 - 実用
JavaScript MochiKit.Async.Deferredは、「現時点ではまた利用できない値」を扱うためのクラスです。 以下のように、コールバックを並べ、イベントを発火させると、各々の返り値が次のコールバックへ渡され実行されていきます。 function increment(value){ alert(value); return value+1; } var d = new Deferred(); d.addCallback(increment); // alert(1) d.addCallback(increment); // alert(2) d.addCallback(increment); // alert(3) d.callback(1); この時、コールバックは以下のようにチェーンを形成しています。(本当はエラーバックも合わせて一つのチェーンを形成しているのですが、
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Reddit - Dive into anything
Parallel Programming Patterns
Index of /~jkondo/DesignPattern
Injecting Dependencies: My Test Classes Want Injection Too
Dependency Injection for Resources