蟻本練習問題の解説をします。今回のトピックは動的計画法です!
今回は難易度が割と混在しているため、水色 〜 青 の方でも解きごたえがある (ありそう、完全に主観) な問題に★をつけました。競技プログラミングにある程度慣れている方も、★がついている問題を解くことをオススメします。
シリーズ目次はこちらからどうぞ。
tsutaj.hatenablog.com
値を覚えて再利用 "動的計画法"
POJ 3176: Cow Bowling
問題リンク
数字が三角形状に並んでいる (詳細はリンク先を見てください)。一番上の数字から、その一段下であって隣接している つの数字のどちらかに降りて行き、一番下に到達したときに終了することを考える。この時に通過した数字の和をスコアとするとき、スコアの最大値を求めよ。
▶表示する
POJ 2229: Sumsets
問題リンク
数字 が与えられるので、要素が の冪乗のみであり、要素の総和が となるような数列の総数を求めよ。ただし、並べ替えて同じになるものは同一視するものとする。
▶表示する
POJ 2385: Apple Catching
問題リンク
リンゴの木が 本あり、時刻 から 秒ごとにどちらかの木からリンゴが落ちてくる。落ちてくるリンゴは、その瞬間に木の下にいるときのみ拾うことができるが、木と木の間は最大で 回までしか移動できない (移動にかかる時間は微小であるとして良い)。あなたは時刻 のとき、 番目のリンゴの木の下にいる。このとき、最大でいくつのリンゴを拾うことができるか?
▶表示する
★ POJ 3616: Milking Time
問題リンク
個の区間がある。 番目の区間 は を満たし、その重みは である。
この区間の中から、区間の間の距離 (右端と左端の距離) が 以上を満たすように選ぶとき、選んだ区間の重み総和の最大値を求めよ。
▶表示する
普通に考えると、 地点 までで 番目までの区間を使うとき、選んだ区間の重み総和の最大値 なる DP が思いつきますが、今回は
で であるため、普通に組むと となり間に合いません。
ここで、 地点 以下 までで 番目までの区間を使うとき、選んだ区間の重み総和の最大値 として (累積 max をとっていることに注意) 、DP の遷移を考えます。
地点 以下について考慮するときの、 番目の区間を使うことによる DP 配列の更新を見ていきましょう。まず、この更新に使われる区間は、 を満たす 番目の区間だけです。なぜなら、 であれば 番目の区間を使えませんし、 であるときも、累積 max をとっていることから の結果をそのまま右へ伝搬させていけば十分だからです。
よって、区間を終端が早い順にソートして、尺取り法のように区間のインデックスを動かしながら解けばよいです。この工夫によって、 で解くことができます。
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
struct Segment {
int l, r, cost;
Segment() {}
Segment(int a, int b, int c) : l(a), r(b), cost(c) {}
bool operator<(const Segment &s) const {
if(r != s.r) return r < s.r;
return l < s.l;
}
};
Segment seg[1010];
int dp[1000010];
int main() {
int N, M, R;
scanf("%d%d%d", &N, &M, &R);
for(int i=0; i<M; i++) {
int l, r, cost; scanf("%d%d%d", &l, &r, &cost);
seg[i] = Segment(l, r, cost);
}
sort(seg, seg + M);
int idx = 0;
for(int i=1; i<=N; i++) {
while(idx < M && seg[idx].r == i) {
int prev = max(0, seg[idx].l - R);
dp[i] = max(dp[i], dp[prev] + seg[idx++].cost);
}
dp[i] = max(dp[i], dp[i-1]);
}
printf("%d\n", dp[N]);
return 0;
}
★ POJ 3280: Cheapest Palindrome
問題リンク
文字列 が与えられる。この文字列に対して、任意の場所に文字を追加、または任意の場所の文字を削除して回文を作りたい。アルファベット を追加するにはコスト が、削除するにはコスト がかかる。回文にするためのコストの最小値を求めよ。
▶表示する
これはいわゆる区間 DP の問題です。普通に難しいと思います・・・。
文字列 の部分文字列 を回文にするためのコストの最小値 とします。答えとなるのは です。
まず、明らかに および が成り立ちます (空文字列および 文字からなる文字列は必ず回文)。ここから範囲を伸ばしたときに、コストがどう変化するのかを見ていくこととしましょう。
区間を左または右に だけ伸ばした状態を考えます。このとき、伸ばしたことによって追加された文字によるコストの増加を考える必要があります。追加と削除の操作があるため面倒に感じると思いますが、実は 追加も削除も実質同じ であることが分かります。なぜなら、 文字のみ追加したため、その区間全体を回文にするためにいま追加した文字に対して何らかの操作をしなければならず、その操作とは「どちらの端にもその文字が来るように文字を足す」か「どちらの端にもその文字が来ないように文字を消す」のどちらかであり、このどちらを取っても回文が作れるからです。つまり、追加コストと削除コストのうち小さい方を選択すれば良いのです。
考えるべき遷移はもうひとつあります。 を左に つ、 を右に つ伸ばしたとします。伸ばしたことによって新たに区間内に入った つの文字が同じ文字であれば、追加コストなしでより長い回文を作れることになります。こちらも忘れないようにしましょう。
ここまで来れば、あとは他の区間 DP の問題と同じように、区間の長さが短いものから順に値を求めていけば良いです。
#include <cstdio>
#include <algorithm>
const int INF = 1 << 25;
int N, M, cost[30], dp[2010][2010];
char buf[2010];
int main() {
scanf("%d%d", &N, &M);
scanf("%s", buf);
for(int i=0; i<N; i++) {
char c; int a, b;
scanf(" %c%d%d", &c, &a, &b);
cost[c-'a'] = std::min(a, b);
}
for(int i=0; i<M; i++) {
std::fill(dp[i], dp[i]+M+1, INF);
dp[i][i] = dp[i][i+1] = 0;
}
for(int len=0; len<M; len++) {
for(int l=0; l<M-len+1; l++) {
int r = l + len;
if(l-1 >= 0 && r+1 <= M && buf[l-1] == buf[r]) {
dp[l-1][r+1] = std::min(dp[l-1][r+1], dp[l][r]);
}
if(l-1 >= 0) {
int nc = cost[buf[l-1] - 'a'];
dp[l-1][r] = std::min(dp[l-1][r], dp[l][r] + nc);
}
if(r+1 <= M) {
int nc = cost[buf[r] - 'a'];
dp[l][r+1] = std::min(dp[l][r+1], dp[l][r] + nc);
}
}
}
printf("%d\n", dp[0][M]);
return 0;
}
漸化式を工夫して高速化
★ POJ 1742: Coins
問題リンク
枚の硬貨があり、 番目の硬貨は 枚硬貨であり、 枚持っている。
いま持っている硬貨だけを使って、 円払うことを考える。ちょうど払える金額は何種類あるか?
▶表示する
これは蟻本 P.62 にある「個数制限付き部分和問題」そのものです。蟻本に書いてあるとおり、bool 値ではない、より多くの情報を持った DP で解きましょう。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M;
int A[110], C[110];
int dp[100010];
int main() {
while(scanf("%d%d", &N, &M)) {
if(N == M && N == 0) break;
for(int i=0; i<N; i++) {
scanf("%d", &A[i]);
}
for(int i=0; i<N; i++) {
scanf("%d", &C[i]);
}
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<=M; j++) {
if(dp[j] >= 0) {
dp[j] = C[i];
}
else if(j - A[i] >= 0 && dp[j - A[i]] > 0) {
dp[j] = dp[j - A[i]] - 1;
}
}
}
int ans = 0;
for(int i=1; i<=M; i++) {
if(dp[i] >= 0) ans++;
}
printf("%d\n", ans);
}
return 0;
}
★ POJ 3046: Ant Counting
問題リンク
数字が 個ある。値が である数は 個あり、同じ数字どうしは区別できない。
この中から 個の数字を選ぶことを考える。すべての についてこの場合の数を求め、その総和を出力せよ。
▶表示する
普通に考えると、 番目までの数字までで 個の数字を選ぶ場合の数 という DP が思いつきますが、工夫しないとこのままでは遅いです。
この DP の遷移は、 のように、連続 要素の和になっています。よって、先ほどの DP の値の累積和を DP 配列に覚えておくことによって、この連続した要素の和の計算が となり、間に合います。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_T = 1000;
const int MAX_K = 100000;
const int MOD = 1000000;
int cnt[MAX_T + 10], dp[MAX_K + 10];
int main() {
int T, A, B, S; scanf("%d%d%d%d", &T, &A, &S, &B);
int t_limit = 0;
for(int i=0; i<A; i++) {
int value; scanf("%d", &value);
cnt[value - 1]++;
if(t_limit < value) t_limit = value;
}
fill(dp, dp+A+1, 1);
for(int i=0; i<t_limit; i++) {
for(int k=A; k>=0; k--) {
dp[k] = (dp[k] - (k-cnt[i]-1 < 0 ? 0 : dp[k-cnt[i]-1]) + MOD) % MOD;
}
for(int k=1; k<=A; k++) {
(dp[k] += dp[k-1]) %= MOD;
}
}
printf("%d\n", (dp[B] - dp[S-1] + MOD) % MOD);
return 0;
}
POJ 3181: Dollar Days
問題リンク
〜 ドルの商品がそれぞれ無限個あり、同じ商品どうしは区別できない。 ドルぴったりを使ってこれらの商品を買うとき、商品の買い方は何通りあるか?
▶表示する
これは蟻本 P.58 の「個数制限なしナップザック問題」そのものです。答えは無駄に 64bit 整数に収まらないため、多倍長整数をつくって頑張ってください・・・。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_DIGIT = 100;
struct BigInt {
typedef long long int ll;
static const ll BASE = 1e17;
vector<ll> buf;
BigInt() {}
BigInt(ll x) {
for(; x; x/=BASE) buf.push_back(x%BASE);
}
BigInt& operator+=(const BigInt &x) {
if(buf.size() < x.buf.size()) buf.resize(x.buf.size());
ll tmp = 0LL;
for(int i=0; i<buf.size(); i++) {
buf[i] += (i < x.buf.size() ? x.buf[i] : 0) + tmp;
tmp = buf[i] / BASE;
buf[i] %= BASE;
}
if(tmp) buf.push_back(tmp);
return *this;
}
void print() {
int S = (int)buf.size() - 1;
for(int i=S; i>=0; i--) {
if(i == S) printf("%lld", buf[i]);
else printf("%016lld", buf[i]);
}
printf("\n");
}
};
int N, K;
int main() {
scanf("%d%d", &N, &K);
vector<BigInt> dp(N+1, 0LL);
dp[0] += BigInt(1LL);
for(int c=1; c<=K; c++) {
for(int i=c; i<=N; i++) {
dp[i] += dp[i-c];
}
}
dp[N].print();
return 0;
}
少し考察を要する問題
★ POJ 1065: Wooden Sticks
問題リンク
個のアイテムがあり、各アイテムには という つのパラメーターが付いている。これらのアイテムを、次の条件を満たすようないくつかの数列に分けることを考える。
を満たす、数列のインデックスの組 について、 かつ が、すべての組に対して成立する (すなわち、数列はどちらのパラメータに対しても単調増加列である)。
このとき、数列の個数を最小化せよ。
▶表示する
LIS の亜種のような問題です。パラメータが つあるので若干厄介ですが、どうすればよいかを考えましょう。
まずどちらか一方の値 (ここでは ) をキーとしてソートします。そうすることによって、 については単調増加性が保証された状態になります。以降、 は無視して考えることとします。
ソートしたものの、依然として に関しては単調増加性がありません。新たに要素 を追加するときに、どこに追加するのが最適でしょうか?
まず、数列の個数を最小化したいため、既存の数列の末尾に繋げられる状況なのに繋げない (新たに数列を作る) のは無駄です。では繋げられる候補が複数個あった場合に、どこに繋げれば良いでしょうか?これは、追加したい要素の値を超えない最大の値をとっているものに繋げるのが最適です。なぜなら、要素を追加することでどれか つの要素の末尾が必ず になりますが、元からなるべく大きな値をとっていたものを に変更し、末尾がより小さいものをキープすることで、後続の要素が既存の数列に繋ぎやすくなるからです。
よって、この問題は で解くことができます。発展的な内容として、ほぼ同様の内容を で行わなければならない問題が存在しますので、ぜひ取り組んでください → D - プレゼント
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = 1 << 25;
typedef pair<int, int> pii;
int main() {
int T; scanf("%d", &T);
while(T--) {
int N; scanf("%d", &N);
vector<pii> v(N);
for(int i=0; i<N; i++) {
int l, w; scanf("%d%d", &l, &w);
v[i] = make_pair(w, l);
}
sort(v.begin(), v.end());
int ans = 0;
vector<int> lis(N);
for(int i=0; i<N; i++) {
int ma = 0, arg = -1;
for(int j=0; j<i; j++) {
if(ma < lis[j] && lis[j] <= v[i].second) {
ma = lis[j];
arg = j;
}
}
if(arg < 0) arg = ans;
lis[arg] = v[i].second;
ans = max(ans, arg + 1);
}
printf("%d\n", ans);
}
return 0;
}
POJ 1631: Bridging signals
問題リンク
定義域、値域ともに である全単射の関数 がある。 かつ を満たすような数列の長さの最大値を求めよ。
▶表示する
これは LIS そのものですので、蟻本 P.63 を読んで実装してみましょう。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1 << 25;
int main() {
int T; scanf("%d", &T);
while(T--) {
int N; scanf("%d", &N);
vector<int> lis(N, INF);
int ans = 0;
for(int i=0; i<N; i++) {
int P; scanf("%d", &P);
int idx = lower_bound(lis.begin(), lis.end(), P) - lis.begin();
lis[idx] = P;
ans = max(ans, idx + 1);
}
printf("%d\n", ans);
}
return 0;
}
★ POJ 3666: Making the Grade
問題リンク
長さ の数列 が与えられる。この数列を、単調増加または単調減少列 に変えることを考える。このときのコストは、 と表される。コストの最小値を求めよ。
▶表示する
この問題において、数列 のとり得る値は で登場した値のみに限定して良いです。なので、 番目までの要素を、 をソートして単調にした数列 の 番目の要素までの値を用いて単調にしたときのコスト最小 という DP を解けばよいです。
これの更新式は、 となります。 の部分は今までの最小を覚えておくことで、効率的に処理できます。
単調増加と単調減少の両方を考える必要がありますが、DP の部分を関数化すると実装が少し楽になります。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long int ll;
const ll INF = 1LL << 60;
int N, a[2010], h[2010];
ll dp[2010][2010];
ll solve() {
for(int i=0; i<N; i++) {
fill(dp[i], dp[i] + N + 1, INF);
}
ll ret = INF;
dp[0][0] = 0;
for(int i=0; i<N; i++) {
ll mi = INF;
for(int j=0; j<N; j++) {
mi = min(mi, dp[i][j]);
dp[i+1][j] = mi + abs(a[i] - h[j]);
if(i+1 == N) ret = min(ret, dp[i+1][j]);
}
}
return ret;
}
int main() {
scanf("%d", &N);
for(int i=0; i<N; i++) {
scanf("%d", &a[i]);
h[i] = a[i];
}
sort(h, h+N);
ll ans = INF;
ans = min(ans, solve());
reverse(a, a+N);
ans = min(ans, solve());
printf("%lld\n", ans);
return 0;
}
問題リンク
個のブロックがある。 番目のブロックは 個あり、ブロック自体の高さが であり、高さ を超える場所に置くことはできない (そのブロックの一部が を超えるのもダメ)
これらのブロックをできるだけ高く積み上げたとき、その高さの最大値を求めよ。
▶表示する
まずそれぞれのブロックについて置ける高さに制限があるため、その制限が厳しいものから順に使えば良さそうです (そのほうがより多く置けるため)。なのでブロックを高さ制限が厳しい順にソートをして、あとは POJ 1742 と同様の方針の DP で解くことができます。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct Elem {
Elem() {}
Elem(int a, int b, int c) :
height(a), alti(b), num(c) {}
int height, alti, num;
bool operator<(const Elem &x) const {
return alti < x.alti;
}
};
Elem es[410];
const int MAX_H = 41000;
int dp[MAX_H + 10];
int main() {
int N; scanf("%d", &N);
for(int i=0; i<N; i++) {
int h, a, c; scanf("%d%d%d", &h, &a, &c);
es[i] = Elem(h, a, c);
}
sort(es, es + N);
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<=MAX_H; j++) {
if(dp[j] >= 0) dp[j] = es[i].num;
else {
int prev_h = j - es[i].height;
if(j > es[i].alti) continue;
if(prev_h >= 0) {
dp[j] = dp[prev_h] - 1;
}
}
}
}
int ans = 0;
for(int i=0; i<=MAX_H; i++) {
if(dp[i] >= 0) ans = max(ans, i);
}
printf("%d\n", ans);
return 0;
}
★ POJ 2184: Cow Exhibition
問題リンク
個のアイテムがある。それぞれのアイテムは つのパラメータ を持っている。
このうちいくつかを選び、パラメータの合計 を最大化したい。しかしこのとき、 かつ でなければならない。これを満たす選び方であるときのパラメータの合計の最大値を求めよ。
▶表示する
通常ならば部分和 DP を解けばよいですが、今回は制約が少々特殊です。
総和を最大化したいので、 の合計が決まっているとき、 の合計は最大値のみわかっていれば十分です。したがって、 番目のアイテムまで見て、 の合計が のときの の合計の最大値 という DP をすれば良いことが分かります。
注意点としては、 の総和が非負でなければならないことを踏まえて、最初に総和をできるだけ大きくするために、 の値が大きい要素から順に DP をする必要があります。これを忘れると、例えば の値が -3 5
という順番であったとき、-3
の要素は総和が非負なので選ばれず、それによって合計が 2
の状態が勘定されないなどの問題が発生します。
#include <cstdio>
#include <utility>
#include <algorithm>
#include <functional>
using namespace std;
typedef pair<int, int> pii;
int N;
pii elem[110];
const int MAX_S = 100000;
const int INF = 1 << 25;
int dp[MAX_S + 10];
int main() {
scanf("%d", &N);
for(int i=0; i<N; i++) {
int a, b; scanf("%d%d", &a, &b);
elem[i] = make_pair(a, b);
}
sort(elem, elem + N, greater<pii>());
fill(dp, dp + MAX_S + 10, -INF);
int ans = 0;
dp[0] = 0;
for(int i=0; i<N; i++) {
int val_a = elem[i].first, val_b = elem[i].second;
if(val_a >= 0) {
for(int k=MAX_S; k>=val_a; k--) {
if(dp[k-val_a] == -INF) continue;
dp[k] = max(dp[k], dp[k-val_a] + val_b);
if(dp[k] >= 0) ans = max(ans, k + dp[k]);
}
}
else {
for(int k=0; k<=MAX_S+val_a; k++) {
if(dp[k-val_a] == -INF) continue;
dp[k] = max(dp[k], dp[k-val_a] + val_b);
if(dp[k] >= 0) ans = max(ans, k + dp[k]);
}
}
}
printf("%d\n", ans);
return 0;
}
次回はデータ構造の問題を解説します!