動的計画法の実例: QRコードの最適なエンコードを求める - Qiita
はじめに 最近、実生活で競技プログラミングが役に立ちました。 趣味の一環で長方形のQRコードであるrMQRコードを生成するPythonパッケージを作成しています。その中で「ビット列が最も短くなるようにデータをエンコードする」という処理に動的計画法を用いました。大学時代に競技プログラミングをやっていた身としては「競プロが役に立った！」と嬉しかったので、実例として共有したくてこの記事を書いています。動的計画法のDPテーブルの定義から遷移のしかた、解の復元までを図や実装とともに説明しています。動的計画法自体は説明していません。実装の全体はこちらでご覧いただけます。 この記事に出てくるrMQRコードの仕様に関する記述はISO規格1に基づいています。最適なエンコードを求めるアルゴリズム自体は仕様に含まれるものではなく、オリジナルのものになります。 ※QRコードは(株)デンソーウェーブの登録商標です。
動的計画法によるDVDのディスク分割の改善
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
LISの計算について - noshi91のメモ
LISは競プロでも低くない頻度で出現する題材です。 一般に知られている計算方法では単純な配列を用いてO(NlogN)でLISの計算が可能ですが、BITを用いることで同じ計算量でより直感的に(個人差あり)LISの計算が可能なのでそれについて少し書きます。 与えられた数列をAとします。 まずDP配列 B を用意し ・B_i ＝A_iを最後尾にしたLISの最大長さ と定義します。 すると ・B_i ＝max( {B_k | 0<=k<i, A_k<A_i } ) + 1 と計算することができます。これは2次元クエリなので一般にNlog^2N掛かってしまいますが、B_iを計算する順番を工夫することによってもっと簡単に高速化が可能です。 すなわちBを0で初期化し、Aの値が小さい順にB_iを計算していきます。すると、条件のうち(A_k<A_i)が不要になります。何故なら、現在見ている値より大きい値を持
確率DPを極めよう - 確率と期待値の問題解説
DP tsutaj (@_TTJR_) Hokkaido University B4 February 20, 2018 tsutaj (Hokkaido Univ.) DP February 20, 2018 1 / 54 1 2 ( ) ( ) HSI 3 4 RareItems (Hard) 5 tsutaj (Hokkaido Univ.) DP February 20, 2018 2 / 54 (Dynamic Programming) tsutaj (Hokkaido Univ.) DP February 20, 2018 3 / 54 DP DP DP tsutaj (Hokkaido Univ.) DP February 20, 2018 4 / 54 A P(A) = A : 6 1 5 P(x ≥ 5) = 1+1 6 = 1 3 A P(Ā) = 1 − P(A)
動的計画法高速化テクニック（オフライン・オンライン変換） - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 以下の問題を考えます． １次元の直線上に地点 $x[0] < x[1] < \cdots < x[n-1]$ がある．我々は車を用いて地点 $x[0]$ から地点 $x[n-1]$ まで移動したい．途中の地点で休憩することができるが，頻繁な休憩も過剰な運転も避けたいので，休憩を挟まずに移動する距離がおよそ $a$ 程度になるようにしたい．具体的には休憩を挟まずに距離 $b$ だけ移動したとき，ペナルティとして $(b - a)^2$ がかかるとし，全体のペナルティが最小になるように移動したい．どのようにすればよいか． この問題は以下の動
子から異なる2つを選ぶ感じの木DPを解くアレ - よすぽの日記
子から異なる2つを選ぶ感じの木DPを解くアレを解くテクニックを紹介します。 D: Longest Path - Indeedなう（オープンコンテスト） | AtCoder とかが簡単に解けたりします 頂点0を根とする根付き木について 頂点iはa[i]を持つ(a[i] >= 0) 頂点iそれぞれについて、b[i] = a[i] + max(0, max(b[x] ただしxはiの子), max(b[x] + b[y] ただしx, yはどちらもiの子でかつx != y)) b[0]を求めよ という問題を考えます つまり、b[i]は子供から0, 1, 2個選んだ時のb[選んだ頂点]のsumのmaxにa[i]を足したものですね vector<int> g[MAX_V]; //g[p]は頂点pの子供を入れたvectorとする int a[MAX_V], b[MAX_V]; void dfs(int p
競技プログラミングにおける全方位木DP問題まとめ - はまやんはまやんはまやん
全方位木DP よく分かる解説 問題 CSA Connected Tree Subgraphs [解説 CF397 Tree Folding CF405 Bear and Tree Jumps AtCoder Driving on a Tree CSA Root Change EDPC Subtree 解説 CF Centroids 解説1 解説2 解説3 CF395 Timofey and a flat tree CF302 Road Improvement 解説 yukicoder No.768 Tapris and Noel play the game on Treeone 解説 違うけど方針が似ている問題 CF Nearest Leaf
CS Academy: Connected Tree Subgraphs - pekempey's blog
問題ページ modified 2018年12月21日 map を使ったこれはあやまりですので、キをつけてください。 modified 2018年12月17日 map を使うと書きやすいらしい。たとえば height を求めるには次のように書けばよい。 map<int, int> dp[100000]; vector<int> g[100000]; void dfs(int u, int p) { if (dp[u].count(p)) return; dp[u][p] = 0; for (int v : g[u]) if (v != p) { dfs(v, u); dp[u][p] = max(dp[u][p], dp[v][u] + 1); } } 解法 $O(n^2)$ 解法は TDPC の木という問題と同じ。 dp[v]:=vの部分木の番号の振り方を計算する。子が a,b,c,d だ
蟻本シリーズ 1 ナップサック問題 - StatModeling Memorandum
「プログラミングコンテストチャレンジブック [第2版]」（通称：蟻本）という本がとてもよかったので、これから3回にわたって統計モデルを絡めた感謝の記事を書こうと思います。 プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ 作者:秋葉拓哉,岩田陽一,北川宜稔発売日: 2012/01/28メディア: 単行本（ソフトカバー） 競技プログラミングはたまに実務で役に立たないとか言われていますが、僕はまったくそうは思いませんでした。プログラマーとしてもデータ解析者としても有益な考え方が満載で、ふと気づけば応用できる対象は至る所にあるように思いました。 今回は以下のナップサック問題と呼ばれる問題を考えます。 重さと価値がそれぞれWeight[i], Value[i]であるようなN個の品物があります。これらの品物から、重さの総和がMax
動的計画法入門（数え上げ） - ペケンペイのブログ
数え上げ系の 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'))
近似文字列アルゴリズムのgestalt pattern machingについてメモ
Google 検索でタイポをすると、意図したであろう綴りを教えてくれたり、意図通りの検索結果を返してくれる。 このスペルチェック機能では、入力文字列が本来の文字列とどのくらい似ているのかを評価するアルゴリズムが肝で、編集距離のアルゴリズムはよくしられている。 ふとしたことから、Ratcliff/Obershelp pattern recognition(gestalt pattern maching ともいう) という編集距離とは別のアルゴリズムに出くわした。 このアルゴリズムは1980年代から存在するが、より利便性の良いアルゴリズムが発明されていったからなのか、wikipedia に載っていないくて、手元のアルゴリズム本にもみあたらない。 まだこのアルゴリズムが輝いていた 1988 年に、 Dr. Dobb’s Journal に発表された次の記事(サンプル実装はアセンブリ言語!)を元に
高速な編集距離の計算方法 - Qiita
今日紹介するコードはここにおいてあります。 https://gist.github.com/aflc/6482587 編集距離（levenshtein距離）の計算方法で一番有名なのが動的計画法を使ったもので、これはWikipediaにも載っているお手軽でよく使われているものです。 しかし、この方法は結構時間がかかるので、他にも高速な手法がいくつか提案されています。 NOXさんのブログエントリを読んでいただくのが一番手っ取り早いのですが、ビットパラレル法というのが上手くハマると10倍以上高速です。 ここで紹介されている論文では64文字以上の比較ができないのですが、今回は Heikki Hyyrö, "Explaining and extending the bit-parallel approximate string matching algorithm of Myers", 2001 と
もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら -
2014年7月30日より8月27日まで開催した、paizaオンラインハッカソン（略してPOH![ポー！]）Lite「天才火消しエンジニア霧島 もしPMおじさんが『丸投げ』を覚えたら」ですが、どのような解法が有ったのでしょうか。 今回もPOH恒例の「解説図解」を、天才火消しエンジニア霧島が解説するとしたら、という体で書いてみたいと思います。(特に文体とか変えませんがｗ 最後に霧島壁紙DLが有るので是非最後までお読みください。) ■どのような高速化ステップがあるのか？ 今回の問題ですが、実行時間に大きく影響する計算量別にみたアプローチでは、すべての組み合わせを出して、人数を満たして一番安い組み合わせを見つける全探索[計算量はO(2^N)]と、動的計画法[計算量はq = max(q_i) としてO(Nq) ]（やり方によってはO(NM)）による2種類があります。 また全探索を改良し、効率的な枝刈
Typical DP Contest ひとこと解法集
rng_2 @rng_58 B: dp[i][j]: 左の山が i 個、右の山が j このこっている状態からスタートするときの先手の取るものの価値の和 2013-09-01 01:22:45
「大きなナップサック」問題解説＆最終成績発表～神級到達者30名！ #アルゴリズム｜CodeIQ MAGAZINE
出題者Ozyさんによる「大きなナップサック」問題の解説記事です。 最適解を導くためのアルゴリズムについてわかりやすい図解付きで説明してくれています。 そして、神級到達者はなんと30名！ニックネームを公開していますよ！ by CodeIQ運営事務局 はじめに 出題者のOzyです。大きなナップサック問題解説です。 今回解説するのは、ナップサック問題の中でも“単一制約の01ナップサック問題”と呼ばれる種類のものです。ちょっと長いですから、今後は単に“ナップサック問題”と表記します。ナップサックに入れる品物には、値段と重量の2要素があり、重量が“制約”に相当します。また、品物1つひとつについては、ナップサックの中に、入れる／入れないという2つの状態がありますので、これは0と1で表現できることから、“01”と呼ばれています。 大きめのナップサック問題を解く場合に用いられる手法として有名なものは、動的
数え上げ問題集 ver.0 - tozangezan's diary
数え上げ問題集 数え上げの問題をある程度まとめます。といっても多すぎて面倒なので、まとまって存在するものはリンクを張ります。 また、検索の都合上「答えを1000000007で割った余りを求める」以外の形式の数え上げは見落とされがちなので、そこらへんは割り切ってください。 まとまって存在するリスト(数え上げをたくさん解きたい人用) http://codeforces.com/problemset/tags/combinatorics 数え上げばっかり集めてあります http://community.topcoder.com/tc 多すぎる上ローカルに保存してなくて調べるのが面倒なので、自分で調べてください。 参考までに、感じる難易度をTopCoder Div1の点数に換算して書いておきます。 良問には☆をいくつか付けます。 AOJ 2333 (500) ☆ AOJ 2335 (650) AO
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Wagner–Fischer algorithm - Wikipedia
Private Presentation
動的計画法入門(An introduction to Dynamic Programming)
Amazon.com: Combinatorial Optimization (Algorithms and Combinatorics, 24): Schrijver, Alexander: Books
