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次元配列だろうが何だろうがビビらない | SRM551 Div2 Hard, 桁DP |
| 一つ前にしか依存しないDPテーブルは2テーブルを使いまわす | int prev=i%2,next=prev^1;dpdp[next][(x+i)%N][y-1] += dpdp[prev][x][y]; | SRM 502 Div2 Hard |
| 最小手数といえば幅優先探索 | | SRM 509 Div2 Hard |
| A以上B以下のもの | f(n):=n以下の条件を満たす非負整数の総数とすればf(B)-f(A-1) | 桁DP |
講評 †
| 問題 | どんな問題か | 理解度 |
| SRM 502 Div2 Hard | 簡単な動的計画法。メモリ節約法。 | 分かるが通ってない（解答） |
| SRM 502 Div2 Hard | 基本の動的計画法。 | 分かるが通ってない(解答) |
| SRM 509 Div2 Hard | 簡単め動的計画法、幅探索。 | 分かってない。ダイクストラとDPと幅探索と幅探索でいけるっぽい |
Topcoder †
- div2 Hard は難易度的には div1 medium より簡単なイメージ
Topcoder環境設定 †
- codeprocessorで何故か必要な部分がカットされちゃう
- 変なことがあったら、一旦Removeしてもう一回設定しないと変更が反映されない
- Options -> Setup User Preferences -> Editors -> Default Language
問題の見方 †
- google翻訳に問題文を突っ込む
- 原始的順像
- 具体的な簡単な問題を自分の手で解こうと試みる。問題の概要を把握する。
- 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
- その他、貪欲でいけるかなど、発想重視で色々考える。
- 求められる情報量の確認
- 特性関数の作りやすさ
- この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
- 計算量
- アルゴリズムに要求される計算量のキツさを確認する。
- 頑張って実装
- テスト
- 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
Challenge †
- vectorのチャレンジの仕方
hoge,foo,test
- とすると、vector[3]={hoge, foo, test};となる。
- 変なスペースはつけてはならない。
- 最後にカンマをつけてはならない。
虎本まとめ †
- 探索
- n次元の全探索
- グラフの幅優先、深さ優先の全探索
- しかし、格子状の道の最小ステップ経路の場合の数などでは、h*wの格子について
の探索をすることになる→メモリを使ってメモ化することで余分な探索を省く
- 幅・深さ優先のメモ化可能性
- まず、指数関数計算量の探索方法を考えることが重要。その後、複数のルートから同じ計算を行なっていないか（グラフ上で合流する部分はないか）をチェックする。
- 返り値がある形でないとメモ化できない
- 「それ以降に得られる〜」をメモ化する
- メモ化からの漸化式構築＝動的計画法
- 「これまでに得られる〜」をメモ化する
- 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
- 「ありえない組み合わせ」というものが存在する
- DPは指数計算量探索の合流である
- 探索の「状態」と「合流法則」を抽出したものがDPとなる
- まず指数計算量探索を図示してみる
- 丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
- すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
- 状態と合流から自動的にDPが計算できる
| グラフ分析 | メモ化探索 | DP |
| 状態 | ノード | 引数 | DPテーブル添字 |
| 値 | ノードに付属する値 | 返り値 | DPテーブル |
| 遷移 | 上から下への操作 | 再帰関数（更新） | 漸化式（代入演算） |
| 結合法則 | 二つ以上のノードから一つへのリダクション | 再帰関数（結合） | 漸化式（左辺値） |
| 初期条件 | 初めのノード | 境界条件 | 境界条件 |
- 初期条件は初めが決まっていることも、深いところの拘束条件があることもある
- DPでは深いところしか決まっていないとやりづらい
- 場合の数も、初めに自明に決まる場合の数から始めるとDPが楽になる
DP †
A未満の数を数える †
- 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[状態];
}
}
- 初期値
- 空集合に対する場合の数みたいなのって扱われるべき？
- i=0, つまりAが空集合の時の場合の数が自明になる？
- A未満であることが確定している(j = 1)、「空集合」の元である自然数の場合の数は？→0
- A未満であることが確定していない(j = 0)、「空集合」の元である自然数の場合の数は？→1？？？本当に？？？
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
