Haskellで動的計画法を実装する２つの方法 出典： Easily Solving Dynamic Programming Problems in Haskell by Memoization of Hylomorphisms ザ圏論的やり方としては①Dynamorphism、手続き的な方法として②STモナドが挙げられる。 DynamorphismはHylomorphismをメモ化したようなもので、詳しくはlotz氏のサイトを参照してほしい。 Haskellerとしては、Dynamorphismはとても憧れる手法である。しかし、思ったよりも速度が出ない。。 このスクラップに二通りのLCSの解法を記載したが、いずれもTLEであった。 lotz氏によると、メモ化されたデータ構造にはO(n)でしかアクセスできないことが理由とのこと。 この記事では、STモナドによるメモ化再帰を用いた動的計画問題
0. はじめに 動的計画法の解法に対しては、「一次元 DP」や「二次元 DP」といった呼称でよびたくなりがちです。たとえば ${\rm dp}[i] := i$ 番目の地点まで到達するまでの最小コスト というような DP テーブルを用いるような DP1 は一次元 DP であり、 ${\rm dp}[i][w] := N$ 個の品物のうち最初の $i$ 個の品物の中から、重さが $w$ を超えない範囲でいくつか選んだときの、選んだ品物の価値の総和の最大値 というような DP テーブルを用いるような DP2 は二次元 DP である、といった具合です。後者はいわゆるナップサック問題に対する DP として有名ですね！ 二次元 DP の配列を再利用して一次元へ しかし今回は、DP を一次元や二次元とよぶことにあまり意味がないかもしれない...という話をします。たとえばナップサック DP は、なんと実
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
0. ゲームを解くとは 世の中には将棋や、囲碁や、オセロのような複雑で難しいゲームから、マルバツゲームや、割りばしゲームや、立体三目並べのような比較的単純なゲームまで、たくさんの種類のゲームがあります。 この種の二人プレイのボードゲームにはある共通の特徴があります。それは 双方が最善を尽くした場合において、「先手必勝」か「後手必勝」か「引き分け」かが予め決まっている。 そして無限の計算時間と計算機資源さえあれば、それを容易に解析できる。 という点です。このように 「先手必勝」か「後手必勝」か「引き分け」なのかを解析する その必勝手順を求める できれば + α として初期盤面だけでなく、すべての局面について「先手勝ち」か「後手勝ち」か「引き分け」かも特定して最善手も求める という営みが「ゲームを解く」ということであり1、それができたならばそのゲームを「完全に理解した」ということができます。本
NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「動的計画法が好きな人」と呼ばれています。今回は動的計画法を用いて得られた最適解を復元するための汎用的な方法について紹介します。 0. はじめに 動的計画法を用いて効率的に解くことのできる最適化問題は数多くあります。パッと思いつくだけでも ナップサック問題 迷路などの最短路問題 区間スケジューリング問題 音声認識パターンマッチング問題 レーベンシュタイン距離 発電計画問題 分かち書き 隠れマルコフモデル ... などなど、多種多様な分野の問題を動的計画法によって効率よく解くことができます。このように、分野横断的な活用をできることが、動的計画法をはじめとした数理工学的手法の特長であり醍醐味であると常々感じています。今回は動的計画法によって得ら
この記事は 「競プロ!!」競技プログラミング Advent Calendar 2017 の 日目の記事として書かれました。 競技プログラミングをそれなりにやってきた方となれば、動的計画法に触れたことも多いでしょう。今回は、その動的計画法における空間計算量削減テクを色々紹介したいと思います。 普通のナップザック問題 題材として、ごく普通のナップザック問題を考えてみましょう。 容量 のナップザックに、品物をいくつか入れたいと考えています。品物は全部で 個あり、 番目の品物は価値 、容量 です。品物の在庫はそれぞれ 個ずつなので、同じ商品を複数個入れることはできません。ナップザックの容量を超えることなく商品を入れる時、入れた商品の価値の総和の最大値を求めてください。 制約は 時間制限 sec メモリ制限 MB とします。せっかく空間計算量削減の話をするんですから、これくらい厳しくしないとですよね
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
$A$ 以下の非負整数のうち「3の倍数または3の付く」かつ「8の倍数でない」数がいくつあるか求めてみよう。でもいきなりこの問題を解くのは難しいと思うので、 $A$ 以下の非負整数の総数を求める $A$ 以下の非負整数のうち、3の付く数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」の数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」かつ「8の倍数でない」数の総数を求める という4つの問題を順に解くことにしよう。 A以下の非負整数の総数を求める 左から順に数字を決めていこう。 左から 4175 と決めたあとの状況を考えてみる。 ? に入りうる数字は何だろう。これは 0 から 9 のどれでもいい。上から 2 桁目が $A$ より小さいので ? に何を選んでも $A$ 以上にはならないからだ。次の場合はどうだろう。 この場合 ? に入りうるのは 0
これは、Competitive Programming Advent Calendar 2016の17日目の記事です。 競技プログラミング（以下，競プロ）においてよく出題される動的計画法（Dynamic programming，通称dp）について，「dpやるだけ」という表現を稀に見かけます．競プロを始めた人のうち，多くの人が（少なくとも自分にとっては）最初の壁のうちの一つと言ってもいいdpというジャンルがなぜ「やるだけ」などというパワーワードを伴ってしまうのか．今回はそういうところから，ふわっと動的計画法について考えてみようと思います．どちらかといえばテクニック的な内容というよりは自分がdpの問題に触れるときに意識しているようなことを書いているだけなので，参考になったりならなかったりすると思いますがご容赦のほど． 動的計画法とは 動的計画法 wikipedia によると「対象となる問題を複
2. 目次 グラフの基礎知識 無向グラフ、有向グラフ 閉路、DAG、トポロジカル順序 グラフの表現方法 DAGの問題の解き方 最短経路、最長経路 最大/最小の重みの合計 連結しているか 動的計画法とDAG DAGを使った動的計画法 問題解説 DAGへの落とし方
数え上げ系の DP について説明する。 この記事は DP 初心者を対象にしている。DP やるだけみたいなことを一度でも考えたことがある人は対象にしていない。 例題 次の問題を考えてみよう。 N 桁以下の 3 の倍数はいくつあるか。 N が小さければ全列挙できる。i 桁の数がすべて列挙できていれば、その後ろに 0～9 を付け足せば i+1 桁の数をすべて列挙できることを使う。 dp[i] := leading zero を含めて i 桁のすべての非負整数の集合 #include <iostream> #include <string> #include <vector> using namespace std; int modulo(string s, int mod) { int ret = 0; for (char c : s) ret = (ret * 10 + (c - '0'))
この記事はCompetitve Programming Advent Calendar 2015の23日目の記事です。tanzakuさんに感謝 www.adventar.org 今回は、累積和を使う動的計画法についてです。TopCoderのDiv2上位ぐらいの人向けの難易度です。 問題 AtCoder Typical DP Conestの問題です。 F: 準急 - Typical DP Contest | AtCoder Problem Statement ある路線には駅 1 から駅 N までの N 個の駅がある。すぬけ君は、この路線に準急を走らせることにした。 準急は、駅 1 に止まり、{駅 2, ..., 駅 N-1} の部分集合に止まり、駅 N に止まる。 連続する K個以上の駅に止まると、客が飽きてしまうので、そのようなことはしない。 準急の停車駅の組み合わせとして何通り考えられる
これで全部の問題に解説をつけられた。 解くより解説書くほうがめんどい…… りんごさんが主催した全問DPのコンテストの、全問題の解説＆ソースコード記事へのリンクです。 コンテストのページはhttp://tdpc.contest.atcoder.jp/ Typical DP Contest A コンテスト - simezi_tanの日記 Typical DP Contest B ゲーム - simezi_tanの日記 Typical DP Contest C トーナメント - simezi_tanの日記 Typical DP Contest D サイコロ - simezi_tanの日記 Typical DP Contest E 数 - simezi_tanの日記 Typical DP Contest F 準急 - simezi_tanの日記 Typical DP Contest G - 辞書順
情報オリンピックという中高生向けの競技プログラミングの大会があります。国内予選・選抜が3回あり、最後に世界大会があります。アルゴリズムの問題が出題されます。予選の毎年のパターンは問1, 2は問題文をコードに起すだけの問題で、問3はアルゴリズムの問題だったり、中学受験的な算数の問題だったりします。問4はいつも動的計画法の問題が出ます。競技プログラミングでは動的計画法が一番の入門であり、これがスタートラインです。これが解けないと始まりません。動的計画法の問題、機械的に解けるのかなと思い色々と考えたのですが、できそうなので、このブログ記事にまとめます。 動的計画法 動的計画法ですが、やはり一番しっかり書かれているのが、書籍「アルゴリズムイントロダクション」 http://www.amazon.co.jp/dp/476490408X です。動的計画法の章は熟読に値すると思います。「動的計画法」とい
Lazy Dynamic Programming Dynamic programming is a method for efficiently solving complex problems with overlapping subproblems, covered in any introductory algorithms course. It is usually presented in a staunchly imperative manner, explicitly reading from and modifying a mutable array—a method that doesn’t neatly translate to a functional language like Haskell. Happily, laziness provides a very n
いやいや、お久しぶりです。 実に半年以上も更新が滞ってました。 ちゃんと生きてます。 以前、動的計画法によるシーケンシャルデータのセグメンテーションという記事を書きましたが、 今回はそれを応用して、テキストセグメンテーションを行おうと思います。 テキストセグメンテーションって？ テキストセグメンテーションとは、文章を意味的な段落に分割することを言います。 例えば、ある1つの文章が、野球の話題→サッカーの話題→尿道結石の話題→また野球の話題 といった具合に話題が推移したとします。 この文章を、これを下図のように話題ごとのセグメントに分割しようってのが、 テキストセグメンテーションです。 ----------------------------------------------------- 今年もペナントレースが始まりました。 去年、セリーグは巨人、パリーグは楽天が優勝。 ・・・ 何はとも
2013-12-12 マニアック動的計画法特集 この記事は Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83) の12日目の記事です。 マニアックな動的計画法(Dynamic Programming, 以下DPと表記)手法についての記事です。 「DP知ってるけど苦手だわ〜」って方は8日目の診断人さんの記事必見です！(http://d.hatena.ne.jp/shindannin/20131208/1386512864) 前書き DPとはなにか、一言でいうと「手法」だと思います。 二分探索や貪欲法と同じようにいろいろな問題に適用できる「手法」であり、 なにかひとつの「アルゴリズム」ではありません。 そういう訳
この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。 動的計画法(Dynamic Programming, DP)についての記事です。 12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました 12/11 前編の図２つを差し替えました。 はじめに まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。 プログラミングコンテストでの動的計画法 http://www.slideshare.net/iwiwi/ss-3578511 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
