第4回競プロ勉強会

はじめに

競プロ勉強会第4回です。今回はDPです。DPは競プロ初心者にとって最初の壁と言われています。今回少し重いですががんばりましょう。

はじめに
1. DPとは
2. メモリ節約
3. DPの高速化
4. 重複してしまうDP
5. 特殊なDP
6. メモ化再帰
7. それでも解けない時は?

1. DPとは

DP、動的計画法とは全探索の際、同じ状態のものをまとめて数え上げていくことで高速化する手法です。言っている事は簡単ですね。ではさっそく有名なナップサック問題について考えましょう。

(問題)n個の重み $w_i$ と価値 $v_i$ の商品がある。この時、重みの総和がW以下となる中で価値の総和を最大化せよ。
但し、n<=100, W<=10000, $w_i$ <=10000, $v_i$ <=10000

まず自然に思いつく方法は $\frac{v_i}{w_i}$ の大きい順に取る貪欲法です。だいたいうまくいきますが、例えば $n=3, W = 4, (w_i, v_i) = (3, 7), (2, 4), (2, 4)$ の時などで失敗しますね。

そこでDPの出番です。

ここで重要な事は、Wが十分小さく、前から順番に取るor取らないを決めていく時、取りうる重みの総和は0からWまでのW+1個のみという事です。(W+1以上は解になりえないので捨てていい)人間の感覚でいうと0からWまで全ての状態を持っておく事はとても無駄な様に見えますが、全探索のO( $2^n$ )に比べたら圧倒的に状態数は少ないです。

それでは具体的にDPを解く手順を説明します。

どの状態でまとめられるかを考える。今回は重みの総和。
前から順番に計算する時、計算量オーダーが間に合うかを考える。
つまり、状態の総数にnを掛けたものが $10^7$ から $10^8$ 程度に収まるか。
数列 $dp\_{i,j}$ を定義する。ここが最も重要。
$dp\_{i,j} :=$ 前からi番目までの商品を使って、重みの総和がjとなる時の価値の最大値
漸化式を立てる。
$dp\_{i,j} = max(dp\_{i-1,j}, dp\_{i-1,j-w\_i} + v\_i)$
左の方はi番目の商品を入れない時、右は入れる時
数式の初期値を考える
簡単の為、商品の番号は0からn-1まででは無く、1からnまでにずらす。
すると $dp\_{0, j} = 0 (j == 0), -INF (otherwise)$ となる。
INFは十分大きい数値。-INFを入れる事でそれが解になる事を防いでる。

追記1) 実際の計算量は遷移の計算量を掛けたものとなる。今回遷移はO(1)だが、漸化式が区間の和やmaxになったりするとその分も考慮する必要がある。
ちょっと難しい問題は前回話したSegmentTreeや累積和を使ったり、遷移を工夫したりする事で高速化するのが多い。

追記2) 今回、漸化式は貰うDPで書いた。貰うDPは $dp\_{i, j}$ を考える時、遷移元はどこかを考えるやり方。
簡単な問題だと貰うDPの方が簡単だけど、遷移が複雑な問題は配るDPで書く方が簡単な時もある。
配るDPとは $dp\_{i-1, j}$ の遷移先はどこかを考えるやり方。配るDPの際初期値の入れ方とかが変わるので注意。
今回だと $dp\_{0, 0}$ 以外の全てに-INFを入れておく。遷移は
$dp\_{i, j} = max(dp\_{i, j}, dp\_{i-1, j})$
$dp\_{i, j+w_i} = max(dp\_{i, j+w_i}, dp\_{i-1, j} + v_i)$

追記3) for文の順序を工夫する事で1次元配列1個だけで求める事も可能。コードは下にあるから考えてみて。でも基本は2次元で考える事。

コードです。

// 貰うDP ver
int n, w[100], v[100], W, dp[101][10001];

int solve() {
  // 初期化
  for (int i = 0; i <= W; i++) dp[0][i] = -INF;
  dp[0][0] = 0;
  
  // 遷移
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= W; j++) {
      if (j >= w[i]) {
        dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
      } else {
        dp[i+1][j] = dp[i][j];
      }
    }
  }

  // 解はdp[n][*]の最大値
  int ans = 0;
  for (int i = 0; i <= W; i++) ans = max(ans, dp[n][i]);
  return ans;
}

配るDPも。

// 配るDP ver
int solve() {
  // 初期化
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= W; j++) dp[i][j] = -INF;
  }
  dp[0][0] = 0;
  
  // 遷移
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= W; j++) {
      dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
      if (j + w[i] <= W) {
        dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i]);
      }
    }
  }

  // 解はdp[n][*]の最大値
  int ans = 0;
  for (int i = 0; i <= W; i++) ans = max(ans, dp[n][i]);
  return ans;
}

せっかくなので1次元DPも。

// 貰うDP 1次元 ver
int solve() {
  // 初期化
  for (int i = 0; i <= W; i++) dp[i] = -INF;
  dp[0] = 0;
  
  // 遷移
  for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
      dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
  }

  int ans = 0;
  for (int i = 0; i <= W; i++) ans = max(ans, dp[i]);
  return ans;
}

何故、for (int j = W; j >= w[i]; j--)の順番なのでしょうか？for (int j = w[i]; j <= W; j++)だとどうなるのでしょうか？

漸化式をよく見てみましょう。jより小さいものの情報を元にjを作っていますね。つまりjが大きいものから更新していくと、更新した情報を使ってバグる事はなくなるわけです。

ちなみに後者の場合求まるものは「各商品は何個でも用いてよい」場合の解になります。考えてみて下さい。

2. メモリ節約

本来2次元DPのものを1次元で表すなどによってメモリを節約できる事があります。上記の例がそうですね。そのような事はあまりないのですが、 $dp\_{i,j}$ の漸化式に $dp\_{i-1,\*}$ しか使われず、1個前の状態さえ持っておけばいい場面はよくあります。その際、 $dp[2][10000]$ のような配列を作り、 $dp[i％2][j]$ のようにアクセスする事でメモリを節約できます。AtCoderではあまりないですが、AOJなどのメモリ制約が小さい問題などで使えるテクニックです。

また、1次元のDPにあえてする事で本質的に計算量が改善される事もあります。

3. DPの高速化

先程説明がありましたが、DPの漸化式を工夫する事で高速化する事は多々あります。

例) $dp\_i = dp\_{i-1} + dp\_{i-3} + dp\_{i-4} + dp\_{i-5} + ... + dp\_0$

はい。i-2を除いて足していますね。普通に足すとO( $n^2$ )かかります。
$sum\_i = dp\_0 + dp\_1 + ... + dp\_i$ とおくと、
$dp\_i = sum\_{i-1} - dp\_{i-2}$
$sum\_i = sum\_{i-1} + dp\_i$
ですね。これを解けばよいです。

例) $a_i, b_i$ が与えられる。 $dp\_{i,j} = dp\_{i-1,j} + a_i (j != b_i), min(dp\_{i-1, k}) (0<=k<n, j == b_i)$

基本的に全体に $a_i$ が足されますね。これは鬱陶しいので、最後にまとめて足す事にします。
すると、 $dp\_{i,j} = dp\_{i-1,j} (j != b_i), min(dp\_{i-1, k})-a_i (0<=k<n, j == b_i)$ となり、jが $b_i$ の時以外は変化しないので1次元のDPにしてSegment Treeなどと一緒に用いる事で高速に解を求める事ができます。

ところで $dp\_j = min(dp\_k + |k - b_i|) (0<=k<n )$ は解けますか?実はこれもSegment Treeを2個持つ事で効率的に解けます。考えてみて下さい。ARCのF問題?であった気がする。

例) $dp\_{i+1,j}=dp\_{i,j} + dp\_{i,j-a_i} + dp\_{i,j-2a_i} + ...$ を解け

もちろん累積和を用いて解けますが、少し考えると $dp\_{i+1,j}=dp\_{i,j} + dp\_{i+1,j-a_i}$ という事がわかりますね。陽に累積和を持たなくても、 $dp\_{i+1,*}$ を用いて求める事ができます。本質的にやっている事は同じです。

まとめると、高速化の手法は

$dp\_{i,j}$ を求めるのに $dp\_{i-1,\*}$ と $dp\_{i,\*}$ を用いて求められないかを考える
累積和を考える
漸化式にmax, minが出るならSegment Treeを考える
配列を使いまわす

4. 重複してしまうDP

例) N個の商品があり、i番目の重さは $w_i$ である。総和がW以下の組み合わせのうち、これ以上商品を入れる事が出来ない状態のもの(極大)は何通りか(N<=200, W<=10000)

$dp_{i,j} := $i番目までの商品を使って総和がjの組み合わせの総数

この定義だと極大の条件を考える事が困難です。こういう時はユニークになる条件に着目して、定義よりきつい制約を設ける事で解ける事が多いです。

考察しましょう。極大の条件を「使っていない商品の中で最も軽いものを入れる事が出来ない」と言い換えても問題ありません。では、使われない中で最も軽いものをXとすると、重さがX未満(!)のものは全て使い、重さXの商品は使えない、それ以上のものは自由に選べますね。

使われない中で最も軽いものはユニークなのでそれを基準に数えましょう。商品を降順にソートして普通にDPします。その際、i番目の商品までのDPを求めた後にi+1番目の商品を使わない時の数え上げをすればよいです。後ろから商品の重さの累積和を持っておけば効率的ですね。

$sum = w\_{i+2}+w\_{i+3}+...+w\_{n-1}$ とおくと $sum + X <= W$ かつ $W < sum + X + w\_{i+1}$ つまり $W-sum-w\_{i+1} < X <= W - sum$ の範囲のXのdp[i][X]を足せばいい

(簡単のため全ての重さは異なる場合で考察しました。同じものが含まれる場合も適当に順番を決めればよいです。)

このように、

ユニークなものに着目
先にソートして大きい/小さい順に見ていく

と解ける場合があります。

5. 特殊なDP

桁DP

最近ABCのE問題くらいでよく見ますね。桁を上からor下から決めていくDPです。上からの方が多いかな。0からn以下の整数のうち???の条件に当てはまるものを数え上げろとか。

上から決めていくと、必要な情報は「今見ている桁」「その数(0-9)」「今までの数はnの上の部分と一致しているかtrue/false」だけです。

bitDP

O(n!)をO( $2^n$ )に落とす。各要素に対して見た/見ていないをbitで管理する。難しくないけどbit操作に慣れていないときついかも？

挿入DP

[1, 2, ..., n]の並び替えを列挙する際、i番目まで決めたってしたくなるけど、何使ったかの情報を持っちゃうとO( $2^n$ )かかる。

代わりに大きい順/小さい順に挿入していく事で何を使ったかの情報を持つのを回避するやり方。賢い。詳細は調べて。

ゲームDP

ゲームの所でいずれやるけど、2人対戦のゲームで乱数がからまず必ず勝敗が決まるものは「初期盤面と先手後手で必ず勝敗が決まります」！将棋やオセロも含まれるけど、状態数が多すぎて調べる事は今は出来ない状態なんですが。

ゲームの取り得る状態数が少ない時、例えば山にコインがあって、何らかのルールで取っていく。最初にコインを取れなくなった人の負け、みたいな状況で、盤面の状態はコインの数程度しかないのでdpで解けるかもしれません。

(但しAtCoderで出るゲームの問題は大抵考察重視の貪欲の問題が多いので見ることは少ないかも)

戻すDP

普通 $dp\_{i-1,\*}$ を元に $dp\_{i,\*}$ を求めるが、最終的に知りたいのが $dp\_{n-1,j}$ の時。
頑張って漸化式いじって $dp\_{i-1,j} = (dp\_{i,\*}, dp\_{i-1,\*}の式)$ にする事で無理やり復元したりできる。賢すぎ。

6. メモ化再帰

再帰関数はきれいに書ける事が多いですが、実行速度が遅い事があります。これの原因は大まかに2つあって、「再帰が内部でスタックを用いているためメモリがO(n)かかる為」、「そもそも無駄な探索をしている為」があります。前者はどうしようもないです(表現力、分かりやすさと速度は両立が難しい...)。一方後者は少しの工夫で高速化できます。

例)以下のプログラムが遅い理由は？

int fib(int n) {
  if (n <= 2) return 1;
  return fib(n-1) + fib(n-2);
}

これは答えの数だけ再帰されます。直感的な説明として、n<=2になるまでずーっと展開され続け、一番下側では1+1+1+...+1が計算されているからです。あまりにも無駄ですね。

fib(n)は一回求めると、それ以降その値を再利用すればいい事は明らかです。

int memo[100000]; // 0で初期化
int fib(int n) {
  if (n <= 2) return 1;
  if (memo[n] > 0) return memo[n];
  return memo[n] = fib(n-1) + fib(n-2); // 代入してreturn
}

この単純な書き換えでO(n)まで改善されます。要はDPと同じで状態をまとめている訳ですね。上のコードは1+1+...+1の形で計算しているけどそれをfib(n)の状態は同じなのでまとめているのです(あえて言語化すると)。

メモ化再帰ができる条件は純粋関数である事、つまり引数を決めるとreturnされる値が一意に定まる、もっと言い換えると関数の外部の変数を参照しない事です。

メモ化再帰、楽だけどグローバルにmemoを置いたりしていて書き方が汚いですね。何かいい書き方はないのかな...(競プロするだけならグローバルに置くのは全然いいですが)

7. それでも解けない時は?

それって実は
二項係数を使う?
貪欲法?
マッチング?
FFT?

本気でDPを勉強したい方はDEGwer氏の数え上げテクニック集を参考にして下さい。