TODO
参考 †
まとめと例題 †
| 方針 | 説明 | 例題 |
| DPテーブルを書いてみて、混み合っている場合は無駄な計算がないか考える | | 2-3 漸化式を工夫する, 個数制限なしナップザック問題 |
| boolのDPは一般に非効率 | | 2-3 漸化式を工夫する, 個数制限付き部分和問題 |
| DPの双対性 | 「状態に対して評価値がどうなるか」⇔「固定された評価値（＝ここでの状態）に対して、最も良い状態（＝ここでの評価値）は何か」 | (2-3 漸化式を工夫する, 01ナップサック問題その2, 最長部分増加部分列問題） |
| 「fの最大化」⇔「命題C(x)=『fがx以上である』が判定可能ならば、xの探索的最大化」 | | 3-2 平均最大化 |
| n回の掛け算はO(log n)で計算可能 | | 3-1 べき乗を高速に計算する |
| 漸化式は行列演算に変換可能 | | 3-5 行列累乗 |
| modはどこでしても同じ | | 3-5 行列累乗, SRM 502 Div2 Hard |
| 集合を、整数型のビット演算を用いてDPの状態に組み込む | | 3-5 ビットDP |
| DPは適切なデータ構造を用いると高速化 | | 3-5 データ構造を用いて高速化 |
| 問題を同値な数学に置き換える | 牛が云々とかいう状態で考えたくない | SRM 502 Div2 Hard |
| DPのデータ型のパターンはいっぱいある | 6次元配列だろうが何だろうがビビらない | SRM 551 Div2 Hard, 桁DP |
| 一つ前にしか依存しないDPテーブルは2テーブルを使いまわす | int prev=i%2,next=prev^1; memset(dp[next], 0, sizeof(dp[next])); dpdp[next][(x+i)%N][y-1] += dpdp[prev][x][y];.絶対，dp[next]を初期化すること！！最後のテーブルの添字は毎回きちんと考えなければならない． | SRM 502 Div2 Hard |
| 最小手数といえば幅優先探索 | | SRM 509 Div2 Hard |
| A以上B以下のもの | f(n):=n以下の条件を満たす非負整数の総数とすればf(B)-f(A-1) | 桁DP |
| n進数の不定長データ列の生成はqueueを使う(A, B, C, AA, AB, ...など) | サンプルコード | SRM 682 Div2 Medium |
| マジックナンバーは消す | バグの温床になる | |
| 負のDP | const int MAX = 1000; int ary[2*MAX + 1]; int *dp = ary + MAX; // [-MAX, MAX]にアクセスできる! | |
| 二段DP | | SRM 523 Div2 Hard |
| DPは問題の制約を気にせず解いて，後でまとめるときに制約を考える | 円卓テーブルで隣り合って同じ色はダメ→同じ色も許容するDPを組んで，後で違う色の場合の数だけ集める | SRM 551 Div2 Hard |
講評 †
| 問題 | どんな問題か | 理解度 |
| SRM 502 Div2 Hard | 簡単な動的計画法。メモリ節約法。 | o（解答） |
| SRM 551 Div2 Hard | 基本の動的計画法。 | o.欲しい情報は定義してしまえ(解答) |
| SRM 509 Div2 Hard | 簡単め動的計画法、幅探索。 | x. 分かってない。ダイクストラとDPと幅探索と幅探索でいけるっぽい |
| SRM 682 Div2 Medium | n進数データ列のqueueによる生成 | o. 通った |
| SRM 682 Div2 Hard | 動的計画法．O(n^4), n=300が愚直だが計算追いつかないので工夫． | x. 計算量が追いつかないところまでは分かったが，どう単純化すればいいか |
| SRM 547 Div2 Hard | 動的計画法+素数+ちょっと工夫 | x(なんか実装ミスってるっぽい). bit操作、set, 解説読むのをやる |
| SRM 523 Div2 Hard | 動的計画法+bit集合+2段DP | x, 状態設定ミスった。分からない。解説 |
| 問題 | どんな問題か | 理解度 |
| SRM 502 Div2 Medium | 確率と文字列操作 | o（bits/stdc++.hとforallを導入） |
Topcoder †
問題の見方 †
- google翻訳に問題文を突っ込む
- 原始的順像
- 具体的な簡単な問題を自分の手で解こうと試みる。問題の概要を把握する。
- 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
- その他、貪欲でいけるかなど、発想重視で色々考える。
- 求められる情報量の確認
- 特性関数の作りやすさ
- この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
- 計算量
- アルゴリズムに要求される計算量のキツさを確認する。
- 頑張って実装
- テスト
- 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
Challenge †
- vectorのチャレンジの仕方
hoge,foo,test
- とすると、vector[3]={hoge, foo, test};となる。
- 変なスペースはつけてはならない。
- 最後にカンマをつけてはならない。
虎本まとめ †
- 探索
- n次元の全探索
- グラフの幅優先、深さ優先の全探索
- しかし、格子状の道の最小ステップ経路の場合の数などでは、h*wの格子について
の探索をすることになる→メモリを使ってメモ化することで余分な探索を省く
- 幅・深さ優先のメモ化可能性
- まず、指数関数計算量の探索方法を考えることが重要。その後、複数のルートから同じ計算を行なっていないか（グラフ上で合流する部分はないか）をチェックする。
- 返り値がある形でないとメモ化できない
- 「それ以降に得られる〜」をメモ化する
- メモ化からの漸化式構築＝動的計画法
- 「これまでに得られる〜」をメモ化する
- 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
- 「ありえない組み合わせ」というものが存在する
- DPは指数計算量探索の合流である
- 探索の「状態」と「合流法則」を抽出したものがDPとなる
- まず指数計算量探索を図示してみる
- 丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
- すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
- 状態と合流から自動的にDPが計算できる
- 初期条件は初めが決まっていることも、深いところの拘束条件があることもある
- DPでは深いところしか決まっていないとやりづらい
- 場合の数も、初めに自明に決まる場合の数から始めるとDPが楽になる
DP †
何を考えるべきか †
- 1セット
- 状態を適当に定めてみる
- 今の状態から次の状態がどう決まるかを考えてみる
- 次の状態が今の状態から統合されるかを考える
- 何の情報が足りないかを考え、情報を状態に追加する
- 注意事項
対応 †
| グラフ分析 | メモ化探索 | DP |
| 状態 | ノード | 引数 | DPテーブル添字 |
| 値 | ノードに付属する値 | 返り値 | DPテーブル |
| 遷移 | 上から下への操作 | 再帰関数（更新） | 漸化式（代入演算） |
| 結合法則 | 二つ以上のノードから一つへのリダクション | 再帰関数（結合） | 漸化式（左辺値） |
| 初期条件 | 初めのノード | 関数呼び出し | 境界条件 |
例：A未満の非負整数を数える †
- 桁DPが入門に非常によいと思う。
- A: N桁の数字
- dp[i][j]: 以下の状態の時の場合の数
- i: 上からi桁目の自然数集合において (i=0, 1, ..., N, inclusive. つまりi=0では空集合を見ている)
- j: A未満であることが確定している (j = 0, 1)
#include <iostream>
#include <string>
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;
const int mod = 1e9 + 7;
int dp[101010][2]; // pos, less
int main() {
string A;
cin >> A;
int n = A.length();
dp[0][0] = 1;
rep (i, n) rep (j, 2) { // DPテーブルの結合則の数 「DPテーブルから決まっていく様子を想像する」というのはこれを思い浮かべること。
int lim = j ? 9 : A[i] - '0';
rep (d, lim + 1) { // DPテーブルの結合則の具体的な計算数。「DPテーブルから決まっていく様子を想像する」というのはこれを思い浮かべること。
(dp[i + 1][j || d < lim] += dp[i][j]) %= mod;
}
// dp[i + 1][0] = dp[i][0]; d[i + 1][1] = (A[i] - '0') * dp[i][0] + 10 * dp[i][1];
// でもいいはず。でも与えられたdによってDPテーブル添字が一意に決まるので、上のようにdで全探索している
}
int ans = 0;
rep (j, 2) (ans += dp[n][j]) %= mod;
cout << ans << endl;
return 0;
}
実装の構造 †
dp[初期状態] = 初期値;
for (状態) {
for (遷移) {
次の状態 = 遷移(状態);
dp[次の状態] = dp[状態];
}
}
- 何となく再帰関数で考えると最後から埋めていきたくなるけど、その必要はない
// ↓のようにコメントを書いておくとよい
dp[i + 1][k][j] = (dp[i][k][j] //i番目は選ばない
+ dp[i][k - 1][(j - i + N) % N]) % MOD //i番目を選ぶ
初期値 †
- 探索がベースの DP はどこから始めれば全列挙ができるか考えると自然に初期値が定まる
- 初期値を定めることは探索ベースの時の関数呼び出しに相当する！初期値
- 初期値はDPの定義外．（そうじゃないと，空集合に対する場合の数みたいなのって扱われるべき？i=0, つまりAが空集合の時の場合の数が自明になる？A未満であることが確定している(j = 1)、「空集合」の元である自然数の場合の数は？→0A未満であることが確定していない(j = 0)、「空集合」の元である自然数の場合の数は？→1？？？本当に？？？みたいな悩み方をすることになる）
- ナップザックのような数え上げの問題では，初期値は0となる．
グラフ理論 †
| 名前 | 計算量 | アルゴリズム | 特徴 |
| ベルマンフォード法 | O(VE) | 前提：負の閉路がない連結グラフ。全辺を見て、現状より辺を通じたほうが良ければ更新。更新するものがなくなるまで行う | 負のコストを許容。負の閉路がなければOK。また、すべての負の閉路の検出も可能（更新が規定回数で止まらなかったら） |
| ダイクストラ法 | O(ElogV) | 前提：負のコストがない連結グラフ。コスト最小の未確定頂点を選び、そこから行ける頂点を更新して未確定頂点とする。これを未確定頂点がなくなるまで続ける。priority queueを使って実装する場合は「確定」の概念が明示的には入らず、コストが同じなら一番初めに処理した頂点が強いことで弾く | 負のコストを許容しない。 |
| 経路復元 | O(E)かO(V) | O(V)は以前の道を記憶する。O(E)は以前の道をあとから探す | E: d[j]=d[k]+cost[k][j]なるkを探す。V: 更新時prev[j]を記録する。 |
| プリム法 | O(ElogV) | 統合頂点群から未統合頂点への最小距離をメモする。未統合頂点のうち統合頂点群に最も近い頂点を探す。統合頂点群に追加する。頂点追加によって、最小距離が変わるので更新する。 | 最も近い頂点を貪欲的に追加する方法 |
| クラスカル法 | O(ElogV) | 辺をコストの小さい順に並べる。コストの低い順に見て、閉路ができないならば連結していく。閉路ができることは連結先と連結元がUnion-Findで同一かによって検知可能 | 最もコストの小さい辺を貪欲的に選び続ける方法 |
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
