【分野別 初中級者が解くべき過去問精選 100 問】を初級者がC++で解く【動的計画法：ナップザック DP】

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】の2-3. 分野別　初中級者が解くべき過去問精選 100 問を初級者がC++で解いていきます。

動的計画法：ナップザック DP

34　ALDS_10_A - フィボナッチ数

再帰だとTLEするので計算結果をメモ化する。vectorに順番に値を保持していくだけ。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int n;
  cin >> n;
  
  vector<int> dp(n + 1);
  dp.at(0) = 1;
  dp.at(1) = 1;
  
  rep(i, 2, n + 1) dp.at(i) = dp.at(i - 2) + dp.at(i - 1);
  cout << dp.at(n) << endl;
}

35　DPL_1_B - 0,1ナップザック問題

ナップサック問題の例題そのままなので簡単。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int N, W;
  cin >> N >> W;
  
  vector<int> value(N), weight(N);
  rep(i, 0, N) cin >> value.at(i) >> weight.at(i);
  
  vector<vector<int>> dp(N + 1, vector<int>(W + 1, -1));
  rep(i, 0, W + 1) dp.at(0).at(i) = 0;
      
  rep(i, 0, N) {
    rep(j, 0, W + 1) {
      if (j >= weight.at(i)) dp.at(i + 1).at(j) = max(dp.at(i).at(j - weight.at(i)) + value.at(i), dp.at(i).at(j));
      else dp.at(i + 1).at(j) = dp.at(i).at(j);
    }
  }
  cout << dp.at(N).at(W) << endl;
}

36　DPL_1_C - ナップザック問題

前問とほぼ同じだが、重複ありで選べるようになっている点が異なる。遷移方法が変わることにかなり戸惑ったが、紙に配列を書いて処理を一つずつ追っていったら理解できた。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int N, W;
  cin >> N >> W;
  
  vector<int> value(N), weight(N);
  rep(i, 0, N) cin >> value.at(i) >> weight.at(i);
  
  vector<vector<int>> dp(N + 1, vector<int>(W + 1, -1));
  rep(i, 0, W + 1) dp.at(0).at(i) = 0;
      
  rep(i, 0, N) {
    rep(j, 0, W + 1) {
      if (j >= weight.at(i)) dp.at(i + 1).at(j) = max(dp.at(i + 1).at(j - weight.at(i)) + value.at(i), dp.at(i).at(j));
      else dp.at(i + 1).at(j) = dp.at(i).at(j);
    }
  }
  cout << dp.at(N).at(W) << endl;
}

37　DPL_1_A - コイン問題

重複ありのナップサックとほぼ同じ。今回は実装時の配列を1次元にしてみた。
頭がこんがらがったので普通に2次元でやればよかった。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int n, m;
  cin >> n >> m;
  
  vector<int> coins(m);
  rep(i, 0, m) cin >> coins.at(i);
  
  vector<int> dp(n + 1, 99999);
  dp.at(0) = 0;
  
  rep(i, 0, m) {
    rep(j, 1, n + 1) {
      if(j >= coins.at(i)) dp.at(j) = min(dp.at(j), dp.at(j - coins.at(i)) + 1);
    }
  }
  cout << dp.at(n) << endl;
}

38　ALDS_10_C - 最長共通部分列

dp.at(i).at(j)でXのi文字目までとYのj文字目までの共通部分列の長さを表現する。dpの問題は、dpテーブルで何を表現するかさえ思いつけば、あとは簡単なのかもしれない、と思い始めた。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int q;
  cin >> q;
  
  rep(i, 0, q) {
    string X, Y;
    cin >> X >> Y;
    
    int xs = X.size();
    int ys = Y.size();
    
    vector<vector<int>> dp(xs + 1, vector<int>(ys + 1, 0));
    rep(i, 0, xs) {
      rep(j, 0, ys) {
        if (X.at(i) == Y.at(j)) dp.at(i + 1).at(j + 1) = dp.at(i).at(j) + 1;
        else dp.at(i + 1).at(j + 1) = max(dp.at(i + 1).at(j), dp.at(i).at(j + 1));
      }
    }
    cout << dp.at(xs).at(ys) << endl;
  }
}

39　JOI 2011 予選 4 - 1 年生

i番目の数を選んだ場合に答えがjになる組み合わせの数をdpテーブルで表現した。難しくはなかった。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int N;
  cin >> N;
  
  vector<int> A(N);
  rep(i, 0, N) cin >> A.at(i);
  
  vector<vector<ll>> dp(N - 1, vector<ll> (21, 0));
  dp.at(0).at(A.at(0)) = 1;
  rep(i, 0, N - 2) {
    rep(j, 0, 21) {
      if (dp.at(i).at(j) != 0) {
        if (j - A.at(i + 1) >= 0) dp.at(i + 1).at(j - A.at(i + 1)) += dp.at(i).at(j);
        if (j + A.at(i + 1) <= 20) dp.at(i + 1).at(j + A.at(i + 1)) += dp.at(i).at(j);
      }
    }
  }
  cout << dp.at(N - 2).at(A.at(N - 1)) << endl;
}

40　JOI 2012 予選 4 - パスタ

めちゃくちゃ難しくて過去イチで悩んだ。詰まって解答を調べても全然理解できなかった。初期状態を何で始めればいいのか分からなくて時間を取られた。結果的には「dp.at(0).at(0).at(0) = 1;」でよかった。dpテーブルの更新部分は「n-2日にiを選んでいる & n-1日にjを選んでいる & n日にkを選ぶ」を表現している。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

#define MOD 10000

int main() {
  int N, K;
  cin >> N >> K;
  
  vector<int> A(10010, 0);
  rep(i, 0, K) {
    int a, b;
    cin >> a >> b;
    A.at(a - 1) = b;
  }
  
  vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(4, vector<int>(4, 0)));
  dp.at(0).at(0).at(0) = 1;
  rep(n, 0, N) {
    rep(i, 0, 4) {
      rep(j, 0, 4) {
        rep(k, 1, 4) {
          if (A.at(n) != 0 && A.at(n) != k) continue;
          if (i != j || j != k) {
            dp.at(n + 1).at(k).at(j) += dp.at(n).at(j).at(i);
            dp.at(n + 1).at(k).at(j) %= MOD;
          }
        }
      }
    }
  }
  
  int ans = 0;
  rep(i, 1, 4) {
    rep(j, 1, 4) {
      ans += dp.at(N).at(i).at(j);
      ans %= MOD;
    }
  }
  
  cout << ans << endl;
}

41　JOI 2013 予選 4 - 暑い日々

i日目に服jを着た場合の「派手さの差の絶対値の合計」の最大値をdpテーブルで表す。i日目に服jを、i+1日目に服kを着られるなら値を更新する。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int D, N;
  cin >> D >> N;
  
  vector<int> T(D);
  rep(i, 0, D) cin >> T.at(i);
  
  vector<int> A(N), B(N), C(N);
  rep(i, 0, N) cin >> A.at(i) >> B.at(i) >> C.at(i);
  
  vector<vector<int>> dp(D, vector<int>(N, 0));
  rep(i, 0, D - 1) {
    rep(j, 0, N) {
      if ((T.at(i) < A.at(j)) || (B.at(j) < T.at(i))) continue;
      rep(k, 0, N) {
        if ((T.at(i + 1) < A.at(k)) || (B.at(k) < T.at(i + 1))) continue;
        dp.at(i + 1).at(k) = max(dp.at(i).at(j) + abs(C.at(j) - C.at(k)), dp.at(i + 1).at(k));
      }
    }
  }
  
  int mx = 0;
  rep(i, 0, N) mx = max(mx, dp.at(D - 1).at(i));
  cout << mx << endl;
}

42　JOI 2015 予選 4 - シルクロード

dpテーブルはi日目に都市jにたどり着いている場合の疲労度の最小値を表す。解法はすぐに思いついてコードも書けてテストケースも合っているのに、WAになって悩み続けてしまった。intだと途中でオーバーフローしていたのが原因だった。計算途中で値の制約を考慮に入れていないとこうなる。

dpの書き方を、配る遷移形式から貰う遷移形式に変えてみた。dpの遷移をイメージするのが苦手だったけど、貰う遷移形式にしたら急に書きやすくなった。初期状態で場合分けしてるのなんかダサいけど、分かりやすいからまあいいや。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define rrep(i, b, a) for (ll i = b; i >= a; i--)
#define repb(i, n) for (ll i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  ll N, M;
  cin >> N >> M;
  
  vector<ll> C(N), D(M);
  rep(i, 0, N) cin >> C.at(i);
  rep(i, 0, M) cin >> D.at(i);
  
  vector<vector<ll>> dp(M, vector<ll> (N, inf));
  rep(i, 0, M) {
    rep(j, 0, N) {
      if (((M - i) < (N - j)) || ((i) < (j))) continue;
      
      if (j == 0) {
        if (i == 0) dp.at(i).at(j) = D.at(i) * C.at(j);
        else dp.at(i).at(j) = min(D.at(i) * C.at(j), dp.at(i - 1).at(j));
      }
      else {
        dp.at(i).at(j) = min(dp.at(i - 1).at(j - 1) + D.at(i) * C.at(j), dp.at(i - 1).at(j));
      }
    }
  }
  
  cout << dp.at(M - 1).at(N - 1) << endl;
}

43　パ研杯2019 D - パ研軍旗

全然思いつかなかった。dpテーブルを入力と同じ5*Nで考えてしまった。公式解説を見たら、dpテーブルの行を「どの色を選ぶか」にしていて、なるほどなーと感動した。それさえ分かれば実装は一瞬だった(なんか無駄が多い書き方だなとは思うけど)。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int N;
  cin >> N;
  
  vector<vector<char>> vec(5, vector<char> (N));
  rep(i, 0, 5) {
    rep(j, 0, N) {
      cin >> vec.at(i).at(j);
    }
  }
  
  vector<vector<int>> dp(3, vector<int> (N));
  rep(j, 0, N) {
    rep(i, 0, 3) {
      char color;
      if (i == 0) color = 'R';
      else if (i == 1) color = 'B';
      else if (i == 2) color = 'W';
      
      int cnt = 0;
      rep(k, 0, 5) if (vec.at(k).at(j) != color) cnt++;
      
      if (j == 0) dp.at(i).at(j) = cnt;
      else {
        int tmp = 999999;
        rep(k, 0, 3) if (i != k) tmp = min(dp.at(k).at(j - 1), tmp);
        dp.at(i).at(j) = tmp + cnt;
      }
    }
  }
  
  int ans = 99999;
  rep(i, 0, 3) ans = min(dp.at(i).at(N - 1), ans);
  cout << ans << endl;
}

44　AOJ 1167 - ポロック予想

重複ありナップサック問題。最初に提出したときは
「N*Nのdpテーブルを作って、普通バージョンと奇数バージョンで2回dpする」
を各クエリごとにやってしまって、無事エラーになった。最初に全部計算してしまって各クエリに対しては回答するだけ、という風にすればいいというのはいい学びになった。そしてやはりdpテーブルは一次元でよかった。コイン問題で苦しんだせいで避けてしまった。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  vector<ll> dp(1000000, inf);
  vector<ll> dp2(1000000, inf);
  dp.at(0) = 0;
  dp2.at(0) = 0;
  
  rep(i, 0, 1000000) {
    rep(j, 1, 1000000) {
      int tetra = j * (j + 1) * (j + 2) / 6;
      if (i < tetra) break;
      
      dp.at(i) = min(dp.at(i - tetra) + 1, dp.at(i));
      if (tetra % 2 == 1) dp2.at(i) = min(dp2.at(i - tetra) + 1, dp2.at(i));
    }
  }
  
  while (1) {
    int N;
    cin >> N;
    if (N == 0) break;
    
    cout << dp.at(N) << " " << dp2.at(N) << endl;
  }
}

45　AOJ 2199 - 差分パルス符号変調

例によって、dpテーブルをどう置くかが難しく、実装は簡単だった。i番目の入力とコードブックのk番目を選んだときの出力がjで、二乗和の最小値がdpテーブルに保持される。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  while (1) {
    int N, M;
    cin >> N >> M;
    if ((N == 0) && (M == 0)) break;
    
    vector<int> C(M), x(N);
    rep(i, 0, M) cin >> C.at(i);
    rep(i, 0, N) cin >> x.at(i);
    
    vector<vector<ll>> dp(N + 1, vector<ll>(256, inf));
    dp.at(0).at(128) = 0;
    rep(i, 0, N) {
      rep(j, 0, 256) {
        if (dp.at(i).at(j) == inf) continue;
        rep(k, 0, M) {
          ll nj = j + C.at(k);
          if (nj < 0) nj = 0;
          else if (nj > 255) nj = 255;
          dp.at(i + 1).at(nj) = min(dp.at(i).at(j) + (x.at(i) - nj) * (x.at(i) - nj), dp.at(i + 1).at(nj));
        }
      }
    }
    
    ll ans = inf;
    rep(i, 0, 256) ans = min(dp.at(N).at(i), ans);
    cout << ans << endl;
  }  
}