動的計画法：漸化式を工夫して高速化（3題）

C++ 競技プログラミング

漸化式を工夫して高速化をはからなければならない動的計画法の問題。
だいたい最初に思いつく漸化式が、間違っているわけではないけれど効率が悪く、提出するとTime Limit Exceededになる。
そこで、漸化式を改善して時間内に解けるようにしましょうね、というやつだ。

POJ1742: Coins

1742 -- Coins
この問題は別の記事でまとめた。hfuji.hatenablog.jp

POJ3046: Ant Counting

3046 -- Ant Counting

問題概要

T種類の蟻の家族がいて、蟻の家族内では個々の蟻の区別はない。蟻の家族iにはN[i]匹の蟻がいる。全家族を合わせると蟻は合計A匹である。サイズがS以上B以下の蟻のグループが何個作れるかを計算せよ。
1 <= T <= 1000
1 <= Ni <= 100
1 <= S <= B <= A <= 100000

解法

dpを次のように定義しよう。
dp[i][j] = (i番目までのファミリーでサイズjの集合が作れる個数)

漸化式は次のとおり。

dp[i+1][j] = dp[i][j] + dp[i][j-1] + ... + dp[i][j-m]
// ただし m = min(j, N[i])

だが、これは効率が悪いので式変形で工夫する。
和で定義される数列を簡単な漸化式にする方法と同じ要領である。
jをずらした漸化式を二つ並べる。

dp[i+1][j]   = dp[i][j] + dp[i][j-1] + ... + dp[i][j-m(j)]
dp[i+1][j-1] = dp[i][j-1] + dp[i][j-2] + ... + dp[i][j-m(j-1)]

で、両辺を引いて

dp[i+1][j] - dp[i+1][j-1] = dp[i][j] - dp[i][j-N[i]-1]
よって
dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-N[i]-1]
// ただし最後の項はj-N[i]-1 < 0のときには存在しない。

というわけだ。

#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int MOD = 1000000;

int main() {
  // 入力
  // ifstream cin( "test.txt" );
  int t, a, s, b;
  cin >> t >> a >> s >> b;
  int n;
  int N[1001] = {0};
  for (int i = 0; i < a; i++) {
    scanf("%d", &n);
    N[n]++;
  }
  // 計算
  vector< vector<int> > dp(2, vector<int>(b+1));
  dp[0][0] = 1;
  dp[1][0] = 1;
  for (int j = 1; j <= b; j++) {
    dp[1][j] = (j <= N[1]) ? 1 : 0;
  }
  for (int i = 1; i < t; i++) {
    for (int j = 1; j <= b; j++) {
      int k = (i + 1) % 2;
      int l = i % 2;
      if (j - N[i+1] - 1 >= 0) {
        dp[k][j] = (dp[k][j-1] + dp[l][j] - dp[l][j-N[i+1]-1] + MOD) % MOD;
      } else {
        dp[k][j] = (dp[k][j-1] + dp[l][j]) % MOD;
      }
    }
  }

  int sum = 0;
  for (int i = s; i <= b; i++) {
    sum += dp[t%2][i];
    sum %= MOD;
  }

  // 出力
  cout << sum << endl;
}

POJ3181: Dollar Days

3181 -- Dollar Dayz

問題概要

ジョンはNドル持っていて、店には1ドル..Kドルの商品が無数にある。ちょうどNドルで商品を買う組み合わせは何通りあるか求めよ。
1 <= N <= 1000
1 <= K <= 100
例:
5
= 1+1+1+1+1
= 1+1+1+2
= 1+2+2
= 1+1+3
= 2+3
なので、5ドルで1ドル〜3ドルを買う組み合わせは5通り。
（N=5, K=3）

解法

dpを定義する。
dp[i][j] = (iドルで1..jドルの商品を買うときの組み合わせ)

和の最大の数（例ではいちばん後ろの項）に着目すると漸化式が作れる。

dp[i][j] = dp[i-1][1] + dp[i-2][2] + dp[i-3][3] + ... + dp[i-j][j]

で、前問と同じく、jをずらして差を取りましょう。

dp[i][j] = dp[i-1][1] + dp[i-2][2] + ... + dp[i-j][j]
dp[i][j-1] = dp[i-1][1] + dp[i-2][2] + ... + dp[i-j+1][j-1]

両辺の差をとって、

dp[i][j] - dp[i][j-1] = dp[i-j][j]
// つまり、
dp[i][j] = dp[i][j-1] + dp[i-j][j]

というふうになる。

#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const unsigned long long MOD = 100000000000000000;
int main() {
  int N, K;
  cin >> N >> K;
  unsigned long long dp[1000+16][100+16][2];

  for (int j = 0; j <= K; j++) {
    dp[0][j][1] = 1;
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= K; j++) {
      if (i >= j) {
        dp[i][j][0] = dp[i][j-1][0] + dp[i-j][j][0];
        dp[i][j][1] = dp[i][j-1][1] + dp[i-j][j][1];
        dp[i][j][0] += dp[i][j][1] / MOD;
        dp[i][j][1] = dp[i][j][1] % MOD;
      } else {
        dp[i][j][0] = dp[i][j-1][0];
        dp[i][j][1] = dp[i][j-1][1];
      }
    }
  }

  if (dp[N][K][0])
    cout << dp[N][K][0];
  cout << dp[N][K][1] << endl;
}