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;dpdp[next][(x+i)%N][y-1] += dpdp[prev][x][y];。最後のテーブルはrep(i, N)に対してdpdp[N%2][j][k]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
マジックナンバーは消すバグの温床になる
負のDPconst int MAX = 1000; int ary[2*MAX + 1]; int *dp = ary + MAX; // [-MAX, MAX]にアクセスできる!
二段DPSRM 523 Div2 Hard
↑

講評 †

  • 簡潔に。
問題どんな問題か理解度
SRM 502 Div2 Hard簡単な動的計画法。メモリ節約法。x. 分かるが通ってない（解答）
SRM 502 Div2 Hard基本の動的計画法。x. 分かるが通ってない(解答)
SRM 509 Div2 Hard簡単め動的計画法、幅探索。x. 分かってない。ダイクストラとDPと幅探索と幅探索でいけるっぽい
SRM 682 Div2 Mediumn進数データ列の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段DPx, 状態設定ミスった。分からない。解説
↑

Topcoder †

  • div2 Hard は難易度的には div1 medium より簡単なイメージ
↑

問題の見方 †

  1. google翻訳に問題文を突っ込む
  2. 原始的順像
    1. 具体的な簡単な問題を自分の手で解こうと試みる。問題の概要を把握する。
    2. 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
    3. その他、貪欲でいけるかなど、発想重視で色々考える。
  3. 求められる情報量の確認
    • yes-noか、max-minか、numかなど。
  4. 特性関数の作りやすさ
    • この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
  5. 計算量
    • アルゴリズムに要求される計算量のキツさを確認する。
  6. 頑張って実装
  7. テスト
    • 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
↑

Challenge †

  • vectorのチャレンジの仕方 
    hoge,foo,test
  • とすると、vector[3]={hoge, foo, test};となる。
  • 変なスペースはつけてはならない。
  • 最後にカンマをつけてはならない。
↑

虎本まとめ †

  • 探索
    • n次元の全探索
    • グラフの幅優先、深さ優先の全探索
      • しかし、格子状の道の最小ステップ経路の場合の数などでは、h*wの格子について$2^{h+w}$の探索をすることになる→メモリを使ってメモ化することで余分な探索を省く
    • 幅・深さ優先のメモ化可能性
      • まず、指数関数計算量の探索方法を考えることが重要。その後、複数のルートから同じ計算を行なっていないか（グラフ上で合流する部分はないか）をチェックする。
      • 返り値がある形でないとメモ化できない
      • 「それ以降に得られる〜」をメモ化する
    • メモ化からの漸化式構築＝動的計画法
      • 「これまでに得られる〜」をメモ化する
      • 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
      • 「ありえない組み合わせ」というものが存在する
  • DPは指数計算量探索の合流である
    • 探索の「状態」と「合流法則」を抽出したものがDPとなる
    • まず指数計算量探索を図示してみる
    • 丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
    • すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
    • 状態と合流から自動的にDPが計算できる
  • 初期条件は初めが決まっていることも、深いところの拘束条件があることもある
    • DPでは深いところしか決まっていないとやりづらい
    • 場合の数も、初めに自明に決まる場合の数から始めるとDPが楽になる
↑

DP †

↑

何を考えるべきか †

↑

対応 †

グラフ分析メモ化探索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となる．
↑

bit操作 †

操作プログラム
iのn bit目を参照!!(i&(1<<n))
iのn bit目に1を書き込みi=(1<<n))
iのn bit目に0を書き込みi&=^(0<<n))
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS