LIS でも大活躍！ DP の配列使いまわしテクニックを特集 - Qiita
0. はじめに 動的計画法の解法に対しては、「一次元 DP」や「二次元 DP」といった呼称でよびたくなりがちです。たとえば ${\rm dp}[i] := i$ 番目の地点まで到達するまでの最小コスト というような DP テーブルを用いるような DP1 は一次元 DP であり、 ${\rm dp}[i][w] := N$ 個の品物のうち最初の $i$ 個の品物の中から、重さが $w$ を超えない範囲でいくつか選んだときの、選んだ品物の価値の総和の最大値 というような DP テーブルを用いるような DP2 は二次元 DP である、といった具合です。後者はいわゆるナップサック問題に対する DP として有名ですね！ 二次元 DP の配列を再利用して一次元へ しかし今回は、DP を一次元や二次元とよぶことにあまり意味がないかもしれない...という話をします。たとえばナップサック DP は、なんと実
動的計画法によるDVDのディスク分割の改善
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
ゲームを解く！Educational DP Contest K, L 問題の解説 - Qiita
0. ゲームを解くとは 世の中には将棋や、囲碁や、オセロのような複雑で難しいゲームから、マルバツゲームや、割りばしゲームや、立体三目並べのような比較的単純なゲームまで、たくさんの種類のゲームがあります。 この種の二人プレイのボードゲームにはある共通の特徴があります。それは 双方が最善を尽くした場合において、「先手必勝」か「後手必勝」か「引き分け」かが予め決まっている。 そして無限の計算時間と計算機資源さえあれば、それを容易に解析できる。 という点です。このように 「先手必勝」か「後手必勝」か「引き分け」なのかを解析する その必勝手順を求める できれば + α として初期盤面だけでなく、すべての局面について「先手勝ち」か「後手勝ち」か「引き分け」かも特定して最善手も求める という営みが「ゲームを解く」ということであり1、それができたならばそのゲームを「完全に理解した」ということができます。本
意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法 - Qiita
NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「動的計画法が好きな人」と呼ばれています。今回は動的計画法を用いて得られた最適解を復元するための汎用的な方法について紹介します。 0. はじめに 動的計画法を用いて効率的に解くことのできる最適化問題は数多くあります。パッと思いつくだけでも ナップサック問題 迷路などの最短路問題 区間スケジューリング問題 音声認識パターンマッチング問題 レーベンシュタイン距離 発電計画問題 分かち書き 隠れマルコフモデル ... などなど、多種多様な分野の問題を動的計画法によって効率よく解くことができます。このように、分野横断的な活用をできることが、動的計画法をはじめとした数理工学的手法の特長であり醍醐味であると常々感じています。今回は動的計画法によって得ら
桁DP入門 - ペケンペイのブログ
$A$ 以下の非負整数のうち「3の倍数または3の付く」かつ「8の倍数でない」数がいくつあるか求めてみよう。でもいきなりこの問題を解くのは難しいと思うので、 $A$ 以下の非負整数の総数を求める $A$ 以下の非負整数のうち、3の付く数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」の数の総数を求める $A$ 以下の非負整数のうち、「3が付くまたは3の倍数」かつ「8の倍数でない」数の総数を求める という4つの問題を順に解くことにしよう。 A以下の非負整数の総数を求める 左から順に数字を決めていこう。 左から 4175 と決めたあとの状況を考えてみる。 ? に入りうる数字は何だろう。これは 0 から 9 のどれでもいい。上から 2 桁目が $A$ より小さいので ? に何を選んでも $A$ 以上にはならないからだ。次の場合はどうだろう。 この場合 ? に入りうるのは 0
動的計画法入門(An introduction to Dynamic Programming)
- The document contains code and explanations for solving optimization problems using dynamic programming, including calculating minimum costs using a 2D array to store results. - It describes applying dynamic programming to problems involving finding minimum costs for tasks that can be split into subtasks, with the overall cost determined by combining subtask costs. - The code provided shows init
動的計画法入門（数え上げ） - ペケンペイのブログ
数え上げ系の 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個以上の駅に止まると、客が飽きてしまうので、そのようなことはしない。 準急の停車駅の組み合わせとして何通り考えられる
Typical DP Contestまとめ - simezi_tanの日記
これで全部の問題に解説をつけられた。 解くより解説書くほうがめんどい…… りんごさんが主催した全問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 - 辞書順
マニアック動的計画法特集 - めも帳
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 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メ
【Python】動的計画法によるシーケンシャルデータのセグメンテーション - 甲斐性なしのブログ
学生の頃、表題のアルゴリズムを研究に応用しようとしていましたが、すっかり忘れているので、思い出すために改めてPythonで実装してみました。当時は、matlabでfor文を回して実現していましたが、今回は、勉強がてらラムダ式やら再帰呼び出しやらを駆使して書いてみようと思います。 シーケンシャルデータのセグメンテーションとは まず、今回取り上げる問題はどういうものか、等間隔でサンプリングされた離散的な時系列データを例にとって説明します。下図のように、時系列データを個のセグメント分割すると、それぞれのセグメントごとに何らかのスコアが得られるとします。さて、セグメントの境界をどこに置けば、スコアの合計値を最大化できるのでしょう？というのが今回解きたい問題です。 具体的な応用を1つ挙げると時系列データの近似があります。例えば、下図のようにセグメント内の平均値で時系列データを近似し、その二乗誤差平均
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Dynamic Programming: 7 Steps to Solve any DP Interview Problem