ホームに戻る
TopCoder の傾向と対策3(C++編:動的計画法)
0、はじめに
Div2 の Hard はDPの問題が圧倒的に多い気がする。
なのでDPの問題の例題と解き方をまとめてみた。
自分で問題を考えるほど能力が無いので、
実際に TopCoder の SRM から問題を拝借した。
TopCoder なので実行2秒以内でメモリ64MBの制限がある。
ただし 100000007 で割った余りを答えよ、という文は省いた。
もしかすると答えが long long でオーバーフローするかもしれない。
いろんな種類の問題を選んだが解法のバリエーションが豊かである。
DPに慣れるにはひたすら練習するしかないと思う。
以下はすべてDPの問題であるが、もちろんDPでやる前には
解法がグラフや貪欲法である可能性も考える必要がある。
1、偶数組み合わせ
問題
横に1列のマスが並んでいる(最大50個)。
このマスをすべて白か黒に塗っていく。
ただし、黒マスを塗る場合は偶数個隣り合っていないといけない。
白マスは偶数でも奇数でも問題ない。
マスの塗り方は何通りあるか?
例題1:
N = 2
このとき、□□ か ■■ の2通りある。
例題2:
N = 3
このとき、□□□ か ■■□ か □■■ の3通りある。
例題3:
N = 5
このとき、
□□□□□ 、 ■■□□□ 、 □■■□□ 、 □□■■□ 、
□□□■■ 、 ■■□■■ 、 ■■■■□ 、 □■■■■ の8通り。
問題:
N = 30
考え方:
ひとつマスを追加したとき、
黒マスが奇数か偶数かをメモしていけばよい。
何も塗っていない状態では、
黒マスが奇数の場合はそもそも黒マスがないので0通り、
黒マスが偶数の場合は黒マスが0個なので1通りである。
いま黒マスを塗ろうとしているとき、
ひとつ前が黒マスが奇数であれば現在の黒マスが偶数の場合に加算、
ひとつ前が黒マスが偶数であれば現在の黒マスが奇数の場合に加算、
というように更新をかける。
いま白マスを塗ろうとしているとき、
ひとつ前が黒マスが奇数であれば黒マスが奇数個並んでしまうので加算しない、
ひとつ前が黒マスが偶数であれば現在の黒マスが偶数の場合に加算、
というように更新をかける。
最終的に黒マスが奇数個であってはならないので、
黒マスが偶数個である場合が答えになる。
DPでとても重要な要素は2つ。
初期値をどのように置くか?
1回の更新をどのようにするか?
#define N 30
long long dp[N + 1][2];
memset(dp, 0, sizeof(dp));
dp[0][0] = 0;
dp[0][1] = 1;
for(int i = 1; i <= N; i++){
// 黒マスを塗る
dp[i][1] += dp[i - 1][0];
dp[i][0] += dp[i - 1][1];
// 白マスを塗る
dp[i][1] += dp[i - 1][1];
}
cout << dp[N][1] << endl;
2、環っかの組み合わせ
問題
赤、青、緑の石がある。
この石をN個(3〜50個)並べて環を作る。
ただし、同じ色の石は隣り合ってはならない。
同じ色の石は区別されず、環の回転、反転は考えない。
石の並べ方は何通りあるか?
例題1:
N = 3
このとき、RGB,RBG,GRB,GBR,BRG,BGR の6通りある。
例題2:
N = 4
このとき、
RGRB,RBRG,RGBG,RBGB,RGRG,RBRB,
GRGB,GBGR,GBRB,GRBR,GRGR,GBGB,
BRBG,BGBR,BRGR,BGRG,BRBR,BGBG
の18通りある。
問題:
N = 30
考え方:
同じ色が隣り合わないだけならひとつ前の問題と考え方は同じ。
ただし、この問題では環っかの端と端を同じ色で繋いではいけない。
よって、最初の色が何であったかを記録しておく必要がある。
この問題では dp[最初の色][石の数][最後の色]で記録を行う。
最終的にDPを行ったあと最初の色と最後の色が異なるもののみ
答えにすることができる。
#define N 30
int dp[3][50][3];
memset(dp, 0, sizeof(dp));
for(int i = 0; i < 3; i++){
dp[i][1][(i + 1) % 3] = 1;
dp[i][1][(i + 2) % 3] = 1;
}
for(int i = 2; i < N; i++){
for(int j = 0; j < 3; j++){
for(int t = 0; t < 3; t++){
dp[j][i][t] += dp[j][i-1][(t + 1) % 3];
dp[j][i][t] += dp[j][i-1][(t + 2) % 3];
}
}
}
int ans = 0;
for(int i = 0; i < 3; i++){
ans += dp[i][N-1][(i + 1) % 3];
ans += dp[i][N-1][(i + 2) % 3];
}
cout << ans << endl;
3、昇順ソート
問題文:
数列(最大50要素)の数字を移動して昇順に並べ替える。
ただし、移動した数字は数字の数だけコストがかかる。
コストが最小になるときのコストを求めよ。
例題1:
7,1,2,3
であれば 1,2,3 を前に出して最小コストは 6。
例題2:
7,1,2,5
であれば 7 を後ろに下げて最小コストは 7。
問題:
9,1,4,3,2,7,5
考え方:
移動するといっても移動した後は好きな位置に配置できる。
よって、移動させるということは取り除くと考えることと同じ。
問題は「数字を取り除いて昇順の数列を残せ」とも読める。
では、どの昇順の数列を残せばいいだろうか?
これは昇順の数列の数字の合計が最大のものである。
なぜなら取り除く数字の総和が最小であるということは、
残った数列の値の総和が最大であるということになるからである。
これを求めるのにDPを用いる。
記録する値は、
「現在の値をいちばん右端にしてできる最大の数列の総和」
である。
#define N 7
int v[N] = {9, 1, 4, 3, 2, 7, 5};
int dp[N];
memset(dp, 0, sizeof(dp));
for(int i = 0; i < N; i++){
dp[i] = v[i];
for(int r = 0; r < i; r++){
if(v[r] < v[i]){
dp[i] = max(dp[i], v[i] + dp[r]);
}
}
}
int total = 0;
int mx = 0;
for(int i = 0; i < N; i++){
total += v[i];
mx = max(mx, dp[i]);
}
int ans = total - mx;
cout << ans << endl;
4、昇順数列カウント
問題文:
数列(最大50要素)の中から昇順数列を探し出せ。
ただし、昇順数列は途中から始まったり、
途中が抜けたり、途中で終わったりすることはない。
数列の中の昇順数列の数を数えろ。
例題1:
1,3,2,4
であれば 1,3,4 と 1,2,4 の 2 つ。
1,3 や 1,2 や 1,4 や 3,4 や 2,4 は不完全。
例題2:
4,3,2,1
であれば 4 と 3 と 2 と 1 の 4 つ。
数字が1つでも数列とみなして良い。
問題:
9,1,5,3,4,2,7,6,8
考え方:
ある数を右に1つずつ追加していく場合の数を求める。
例えば、1,3,5,2 の右に 4 を追加することを考える。
このときひとつ左の数値は 2 でありこのとき数列の数は増えない。
次にそのひとつ左の数値は 5 でありこれは昇順にならないので無視。
次にそのひとつ左の数値は 3 でありこのとき数列が増える。
つまり、現在の最大値を上回ると数列は追加されることになる。
このようにしてすべての数列の場合を数えることができる。
ただし、数列は途中で終わってはいけないという条件がある。
よって、すべての条件から右端が最大値で終わるもののみに、
限定して場合の数を足し算していけばよい。
#define N 9
int v[N] = {9, 1, 5, 3, 4, 2, 7, 6, 8};
int dp[N];
memset(dp, 0, sizeof(dp));
for(int i = 0; i < N; i++){
int mx = 0;
int count = 0;
for(int r = i; r >= 0; r--){
if(v[r] < v[i] && mx < v[r]){
count += dp[r];
mx = v[r];
}
}
if(count == 0){
count++;
}
dp[i] = count;
}
int ans = 0;
int mx = 0;
for(int i = N - 1; i >= 0; i--){
if(v[i] > mx){
ans += dp[i];
mx = v[i];
}
}
cout << ans << endl;
5、K角形を数えろ
長さの違う(最大50000)複数の棒(最大50)がある。
この棒を使ってK角形(3以上10以下)を作る。
いくつのK角形ができるか?
例題1:
K = 3
1,1,1,1
長さ1の棒が4本あり、三角形を作る。
この場合使用する棒の組み合わせは、
(0 1 2) (0 1 3) (0 2 3) (1 2 3) の4通りがある。
同じ長さであっても棒は区別する。
三角形のどの位置に配置するかの順は区別しない。
例題2:
K = 5
1,1,1,1
棒4本で五角形は作れない。よって0通り。
例題3:
K = 4
1,2,3,4
1通りの四角形ができる。
例題4:
K = 4
1,2,3,6
6 が長すぎるので四角形はできない。0通り。
問題:
K = 5
26,12,12,2,17,5,5,5,7,16,4,13
考え方:
K角形が成立するには、
「最大の棒の長さよりそれ以外の棒の長さの和が大きい」
ことが成り立つ条件である。
よって、まず棒を昇順に並び替える。
DPの更新は次のようにする。
まず 0 本の棒を使ってできる棒の長さの和が0なのは1通り。
DP[0][0] = 1; とする。
例えば、長さ2の棒が1本加えられると、
DP[1][2] = 1 と更新される。
さらに、長さ5の棒が1本加えられると、
DP[1][5] = 1、DP[2][7] = 1 と更新される。
このように更新していけば良い。
ちなみに長さの和が 50000 より大きいものは記録する意味が無い。
棒の長さの最大値が 50000 なのでこれを超える比較は存在しない。
よって、50000 より大きいものはすべて 50001 にメモする。
こうすることでメモリを無駄に使うことが無い。
次に、1からn本目までの長さの和のDPを更新したとき、
さらにn+1本目の棒を追加したときに、
n本の中から K-1 本使った長さの和のそれぞれの場合の数から、
n+1本目の長さより長いものの場合を数えていく。
これはn+1がいちばん長いときの場合として数えているので、
nを更新していくたびに同じことをしていっても重複しない。
#define K 4
#define N 12
int d[N] = {26,12,12,5,17,2,2,2,7,16,4,13};
vector<int> v;
for(int i = 0; i < N; i++){
v.push_back(d[i]);
}
sort(v.begin(), v.end());
long long dp[N+1][50002];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1LL;
long long ans = 0LL;
for(int r = 0; r < v.size() - 1; r++){
for(int t = 10; t >= 1; t--){
for(int s = 0; s < 50002; s++){
if(s + v[r] <= 50000){
dp[t][s + v[r]] += dp[t - 1][s];
}
else{
dp[t][50001] += dp[t - 1][s];
}
}
}
for(int t = v[r + 1] + 1; t <= 50001; t++){
ans += dp[K - 1][t];
}
}
cout << ans << endl;
6、少なくとも1個以上をカウント
問題文:
0番〜N−1番のN個(最大300個)の箱が順に一列に並んでいる。
箱には1個のボールを入れることができる。
A番目からB番目の箱に少なくとも1個のボールが入っている、
という情報が K 個(最低1個以上)与えられる。
このとき箱にボールが入っている状態の場合の数を求めよ。
例題1:
N = 3
A-B = {0-2}
であれば3つの箱があり、
0番から2番の箱に少なくとも1個のボールが入っている。
このとき最低どれかに1個ボールが入っていればよい。
すべてのパターン 8 通りから全て空の 1 通りを除く。
よって、場合の数は 7 通り。
例題2:
N = 3
A-B = {0-1, 1-2}
であれば1の箱にボールが必ず入っていないといけない。
よって、0と1、1のみ、1と2、0と1と2の 4 通り。
問題:
N = 6
A-B = {0-0, 0-2, 1-3, 2-3, 2-4}
考え方:
箱が0個から右に箱を1個ずつ追加していくとどうなるか?と考える。
このとき、1-3 と 2-3 は同じことを言っている。
少なくとも 2-3 に1つあるのであれば、
必ず 1-3 に1つはあるであろう。
よって、この場合は 2-3 のみとみなしても良い。
更新の仕方は、もし新たに追加した箱にボールを入れるのであれば、
過去の入れ方は全部採用できる。
もし、入れないのであれば今回の箱で追加された有効範囲で、
過去の採用方法を更新しなければならない。
例えば、過去3個までの入れ方に制限が無かった場合、
4個目で 2-3 という制限がかかった場合に、
4個目にボールを入れるのであれば過去の方法は問題なく全部使える。
ただし、4個目にボールを入れないと考えると使えるのは3個目の結果だけ。
最初の2個の結果は切り捨てなければならない。
このようにDPを更新していく。
#define N 6
#define K 5
int L[K] = {0, 0, 1, 2, 2};
int R[K] = {0, 2, 3, 3, 4};
int dp[N + 1][N + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 0; i < K; i++){
L[i]++;
R[i]++;
}
for(int i = 1; i <= N; i++){
int ml = 0;
for(int r = 0; r < K; r++){
if(R[r] == i){
ml = max(ml, L[r]);
}
}
for(int r = 0; r < i; r++){
dp[i][i] += dp[i - 1][r];
if(r >= ml){
dp[i][r] += dp[i - 1][r];
}
}
}
int ans = 0;
for(int i = 0; i <= N; i++){
ans += dp[N][i];
}
cout << ans << endl;
7、多くても2個以上をカウント
問題文:
0番〜N−1番のN個(最大300個)の箱が順に一列に並んでいる。
箱には1個のボールを入れることができる。
A番目からB番目の箱に多くても2個以下のボールが入っている、
という情報が K 個(最低1個以上)与えられる。
このとき箱にボールが入っている状態の場合の数を求めよ。
例題1:
N = 3
A-B = {0-2}
であれば3つの箱があり、
0番から2番の箱に多くても2個以下のボールが入っている。
このときすべての箱にボールが入っていると、
0番から2番の範囲のうちにボールが3個になってしまう。
すべてのパターン 8 通りから全てに入っている場合の 1 通りを除く。
よって、場合の数は 7 通り。
例題2:
N = 3
A-B = {0-1, 1-2}
であればどの箱にボールが入っていてもかまわない。。
よって、全通りの 8 通りが答え。
問題:
N = 6
A-B = {0-0, 0-2, 1-3, 2-3, 2-4}
考え方:
左から0番目の箱にボールが入っている場合を考える。
次の1番目の箱にボールが入らない場合と入る場合を考える。
0番目に入っていて現在1番目を考えるので dp[0][1] = 1 とする。
入らない場合は0番目に入っていて次に2番目を考えるので、
dp[0][2] += dp[0][1] となる。
入る場合は1番目に入っていて次の2番目を考えるので、
dp[1][2] += dp[0][1] となる。
ただし、ここで0番目からx番目までは2個以下の制限があるとき、
dp[i][x + 1] += dp[0][1] の更新になる。
これは0番目と1番目にボールがすでに入っているので、
2番目からx番目にはボールが入らないことが確定したため。
これを左から1番目にボールが入っている場合からスタートの場合、
2番目の場合、と1からN−1まですべての場合を更新していく。
この方法ではすべてボールが入っていない場合を考慮しないので、
すべてのDP計算を行ったあとで1を足す必要がある。
int L[K] = {0, 0, 1, 2, 2};
int R[K] = {0, 2, 3, 3, 4};
int dp[N + 1][N + 1];
memset(dp, 0, sizeof(dp));
for(int i = 0; i < N; i++){
dp[i][i + 1] = 1;
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
dp[j][i + 1] += dp[j][i];
int x = i;
for(int t = 0; t < K; t++){
if(j >= L[t] && i <= R[t]){
x = max(x, R[t]);
}
}
dp[i][x + 1] += dp[j][i];
}
}
int ans = 1;
for(int i = 0; i < N; i++){
ans += dp[i][N];
}
cout << ans << endl;
8、最大公約数が1の最大組み合わせ
100以下の数字がN個(最大50個)ある。
この中から互いに最大公約数が1であるK個の数字を選ぶ。
選べるK個の数字の最大の個数を求めよ。
例題1:
2,3,4,5
であれば、2,3,5 の 3 つ。3,4,5 の 3 つでも良い。
2 と 4 は最大公約数が 2 であるので同時に選べない。
例題2:
1,2,4,8
であれば、1,2 か 1,4 か 1,8 で 2 つ。
問題:
10,20,37,42,59,74,80,89,95
考え方:
例えば 10 を選んだ場合、
以降は 2 と 5 の倍数を選ぶことはできない。
よって、10 を素数の掛け算に分解して、
以降その素数で割り切れる数値を使用しなければ良い。
では、10 と 15 があった場合どちらを選ぶべきだろう?
2 と 5 なのか 3 と 5 なのかを選択しなければならない。
実際にはやってみないとわからない。
このどちらを選ぶかをDPを用いて解く。
例えば 10 を選ぶときは 00000101 に記録し、
15 を選ぶときは 00000110 に記録するというようにする。
このような記録法をビットDPという。
よって、1 から 100 までの素数は 26 個なので、
dp[50][1 << 26] というDP配列を用意すれば良い。
ただし、ここで問題が発生する。
(1 << 26) は 67108864 であり、
50 * 67108864 のループは回せない。
解決策として 53 以上の素数は、
100 以下の数値の掛け算の要素にならないことに注目する。
2 * 53 = 106 なので 53 はビットDPの要素にする必要が無い。
また数字の 1 もDPの要素にする必要が無い。
ゆえに 2 から 47 までの素数 15 要素でビットDPする。
dp[50][1 << 15] は 50*32768 なので探索可能である。
ビットDPは要素が50個あれば20ビットくらいが精一杯である。
#define N 9
int v[N] = {10,20,37,42,59,74,80,89,95};
int prime[26] = {
1, 2, 3, 5, 7,11,13,17,19,23,
29,31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97
};
vector<int> v2;
int ans1 = 0;
int ans2 = 0;
for(int i = 0; i < N; i++){
for(int r = 0; r < 26; r++){
if(v[i] == prime[r]){
if(v[i] == 1 || v[i] > 50){
ans1++;
goto f;
}
}
}
v2.push_back(v[i]);
f:;
}
if(v2.size() != 0){
int dp[v2.size()][1 << 15];
memset(dp, 0, sizeof(dp));
vector<int> b;
for(int i = 0; i < v2.size(); i++){
int n = 0;
for(int r = 0; r < 15; r++){
if(v2[i] % prime[r + 1] == 0){
n |= 1 << r;
}
}
b.push_back(n);
}
dp[0][b[0]] = 1;
for(int i = 1; i < b.size(); i++){
// 現在の数値からスタート
dp[i][b[i]] = max(1, dp[i - 1][b[i]]);
for(int r = 0; r < (1 << 15); r++){
if(dp[i - 1][r] != 0){
// 現在の数値は使用しない
dp[i][r] = max(dp[i][r], dp[i - 1][r]);
if((r & b[i]) == 0){
// 可能であれば現在の数値を使用する
dp[i][r | b[i]] = max(dp[i][r | b[i]], dp[i - 1][r] + 1);
}
}
}
}
for(int i = 0; i < (1 << 15); i++){
ans2 = max(ans2, dp[b.size() - 1][i]);
}
}
cout << ans1 + ans2 << endl;
9、2次元配置
問題文:
幅 W(最小1個、最大8個)、高さ H(最小1個、最大100個)
の四角のマスが W×H 個並んでいる。
このマスに○を描き込んでいくのだが、
○を描いた場合には周囲8マスには○を書けない。
○を描き込む方法は何通り存在するか?
ただし、○を1つも書き込まない場合も1つと数える。
例題1:
W=2, H=2
以下の5通り。
□□ ○□ □○ □□ □□
□□ □□ □□ ○□ □○
例題2:
W=4, H=4
314 通り。
問題:
W=8, H=8
考え方:
1次元の場合はほとんどの場合、左から右に更新すれば良い。
ただし2次元では左上から右下に単純に更新することはできない。
■■☆☆☆☆☆☆
☆☆☆□
例えば上図で□に○を描くか描かないかを考えるとき、
☆の部分はまだ確定していない部分といえる。
なぜなら□に○を描いた場合は周囲4つの☆は○で無く、
□に○を描かない場合は周囲4つの☆は○を描く場合もある。
よって、W=8 のとき☆が9個ぶんは中途状態としてメモする。
■は確定している部分である。
この■の位置は□に○を描いても影響をうけることはない。
この解法は W が最大8個であるから可能であるといえる。
例えば W=100, H=100 はこの解法で解くことはできない。
long long dp[101][1<<9];
int w = 8;
int h = 8;
memset(dp,0.sizeof(dp));
int mask = ((1<<(w+1))-1);
dp[0][0] = 1LL;
dp[0][1] = 1LL;
for(int i = 1; i < w*(h+1); i++){
int ny = i / w;
int nx = i % w;
for(int j = 0; j < (1<<(w+1)); j++){
dp[i][(j<<1) & mask] += dp[i-1][j];
// 左端
if(nx == 0){
if((j >> (w-1) & 1) == 0 && ((j >> (w-2)) & 1) == 0){
dp[i][((j<<1)+1) & mask] += dp[i-1][j];
}
}
// 右端
else if(nx == w-1){
if(((j >> (w-1)) & 1) == 0 && ((j >> w) & 1) == 0 && (j & 1) == 0){
dp[i][((j<<1)+1) & mask] += dp[i-1][j];
}
}
// 両端以外
else{
if((j >> (w-2)) == 0 && ((j >> (w-1)) & 1) == 0 && ((j >> w) & 1) == 0 && (j & 1) == 0){
dp[i][((j<<1)+1) & mask] += dp[i-1][j];
}
}
}
}
long long a = 0;
for(int i = 0; i < (1<<(w+1)); i++){
a += dp[w*h-1][i];
}
cout << a << endl;
10、グループ分け
問題文:
N個(最小2個、最大50個)の数字がある。
数字は1から最大60000までの数字である。
この数字を2つのグループに分けたい。
分けるときに基準に基づいて分けていく。
グループ分けには次の2つの基準がある。
片方のグループの数字の和がもう一方の和より大きい。
和の大きいグループから小さいグループに対して
どの1つの数字を移動しても和の大小関係が逆転すること。
このようなグループの分け方は何通りあるか?
例題1:
1,2,3,4
1,2 と 3,4 に分ける場合がある。
1,2 と 3,4 では 3,4 のグループのほうが和が大きい。
大きいグループから小さいグループに 3 を移動すると、
1,2,3 と 4 に分かれグループの和の大小関係が逆転する。
大きいグループから小さいグループに 4 を移動すると、
1,2,4 と 3 に分かれこれもグループの和の大小関係が逆転する。
よって、1,2 と 3,4 は条件を満たす分けかたといえる。
同様に、1,3 と 2,4 で分けるやりかたでも条件を満たす。
ただし、2,3 と 1,4 の分けかたは条件を満たさない。
これは最初の和が互いに等しいため条件を満たさない。
答えは2通りになる。
例題2:
1,1,1,1,1
数字は同じ値であることもある。
この場合 1,1,1 と 1,1 に分ければ条件を満たす。
ただし、すべての 1 は別のものと判断するため。
5つのものから3つを選ぶので5C3通りの選びかたがある。
よって、答えは10通りである。
例題3:
100,1
グループを分けるときグループには最低1つの数字が必要である。
ただし、移動することで数字が無くなっても問題ない。
100 と 1 のグループに分けたとき、
100 を 1 のグループに移動することはできる。
移動するとき大小関係は逆転する。
よって、答えは1通りである。
問題:
8,11,12,12,17,17,17,20,26,31
考え方:
まず2つのグループの和をどう記録するか考える。
このときに各グループの値を記録する必要がありそうだが、
実際には片方のグループの和だけを記録すればよい。
まず最初にすべての数値の和を計算する。
そして片方の数字の和をDPで記録していく。
このときもう一方の和は記録していく必要はない。
もう一方の和はすべての総和から片方の和を引けばよい。
よって、片方のグループの和のみでDPを行うことができる。
では、どの値をもう片方に移動しても大小関係が変わる、
という条件はどうクリアすれば良いだろう?
大きい数字から順に片方の和にDPで追加していく。
このとき追加した値を移動することで大小関係が逆転したとしよう。
これはどの値をもう片方に移動しても大小関係が変わるといえる。
なぜなら大きい数字からDPに追加しているので、
その値までに追加された数字はすべて現在の値以上の数字といえる。
#define N 10
int v[N] = {8,11,12,12,17,17,17,20,26,31};
long long dp[3000001];
int sum = 0;
long long ans = 0LL;
sort(v, v+N, greater<int>());
for(int i = 0; i < N; i++)sum += v[i];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i = 0; i < N; i++){
for(int j = 60000*i; j >= 0; j--){
if(dp[j] != 0){
dp[j + v[i]] += dp[j];
// 移動前で大小比較、移動後で大小比較
if(j + v[i] > sum - (j + v[i]) && j < sum - j){
ans += dp[j];
}
}
}
}
cout << ans << endl;
11、時間内に全到達
問題文:
1直線の座標軸(0以上100万以下)がある。
スタート地点は s である。
ここから指定した地点(最大50個)すべてに到達したい。
座標を1つ移動するたびに時間を1使用する。
スタート地点でも時間は0である。
到達する各地点には制限時間(10億以下)がある。
各地点にはトータル時間で制限時間以下に到達する必要がある。
すべて到達するときの最小時間を求めよ。
すべてに到達できない場合は -1 を答えよ。
例題1:
s = 3
地点 1,4,5
時間 3,5,7
であれば 1 → 4 → 5 の順で移動すれば、
各地点に時間 2 → 5 → 6 で到達できる。
これはすべての地点の制限時間を過ぎていない。
よって最小時間 6 ですべてに到達できる。
例題2:
s = 3
地点 0,2,4,9
時間 18,2,6,16
であれば、2 → 4 → 0 → 9 で時間が 16 で到達できる。
2 → 4 → 9 → 0 でも到達できるが時間は 17 かかる。
よって答えの最小時間は 16 になる。
例題3:
s = 5
地点 2,6,7
時間 7,5,9
であれば、どのようにしてもすべてに到達できない。
よって、答えは -1 になる。
問題:
s = 6
地点 0,2,4,5,8,10,20
時間 19,21,6,31,16,8,98
考え方:
終点は必ず右端か左端になる。
いったん端に行っているのであれば中に戻る必要は無い。
よって、正解は左端か右端のどちらか。
ゆえに左端か右端をDPでメモしていく。
説明の簡単のため、左から 0,1,2 の3地点を考える。
メモリは dp[3][3][2] の3要素を用意する。
1つめは左の地点、2つめは右の地点、
3つ目は 0 であれば左端、 1 であれば右端のメモ。
dp[0][1][0] であれば 1 → 0 と移動したときの時間、
dp[0][1][1] であれば 0 → 1 と移動したときの時間、
を意味する。
dp[1][2][0] であれば 2 → 1 と移動したときの時間、
dp[1][2][1] であれば 1 → 2 と移動したときの時間、
を意味する。
さて、ここで dp[0][2][0] と dp[0][2][1] を求めてみる。
dp[0][2][0] は dp[1][2][0] から 1 → 0 と移動するパターン、
dp[0][2][0] は dp[1][2][1] から 2 → 0 と移動するパターン、
の2つを考え小さいほうをメモする。
dp[0][2][1] は dp[0][1][0] から 0 → 2 と移動するパターン、
dp[0][2][1] は dp[0][1][1] から 1 → 2 と移動するパターン、
の2つを考え小さいほうをメモする。
もちろんこの際に制限時間を満たすか判断する必要がある。
このように小さな幅からどんどん範囲を広げていく。
#define N 7
int s = 6;
int d[N] ={0, 2, 4, 5, 8, 10, 20};
int t[N] ={19, 21, 6, 31, 16, 8, 98};
int dp[N][N][2];
for(int i = 0; i < N; i++){
if(abs(s - d[i]) <= t[i]){
dp[i][i][0] = abs(s - d[i]);
dp[i][i][1] = abs(s - d[i]);
}
else{
dp[i][i][0] = 2000000000;
dp[i][i][1] = 2000000000;
}
}
for(int i = 1; i < N; i++){
for(int j = 0; j < N - i; j++){
int l = j;
int r = j + i;
dp[l][r][0] = min(dp[l + 1][r][0] + d[l + 1] - d[l], dp[l + 1][r][1] + d[r] - d[l]);
if(dp[l][r][0] > t[l]){
dp[l][r][0] = 2000000000;
}
dp[l][r][1] = min(dp[l][r - 1][1] + d[r] - d[r - 1], dp[l][r - 1][0] + d[r] - d[l]);
if(dp[l][r][1] > t[r]){
dp[l][r][1] = 2000000000;
}
}
}
int ans = min(dp[0][N - 1][0], dp[0][N - 1][1]);
if(ans == 2000000000)ans = -1;
cout << ans << endl;
12、回文を作れ
問題文:
ある文字列が与えられる(最大50文字)。
この文字列に対して以下の3つの操作ができる。
1、任意の位置に1文字追加する。
2、任意の位置の1文字消去する。
3、任意の位置の1文字書き換える。
これらの操作は好きな操作を好きな回数だけ好きな順番で行える。
最小の操作回数で回文を作るときの回数を求めよ。
例題1:
"abba"
すでに回文なので回数は 0 回。
例題2:
"abc"
a を c もしくは c を a に書き換えれば良い。
よって最小回数は 1 回。
例題3:
"abcdfgdcbz"
g を消去して z を a に書き換えれば良い。
よって最小回数は 2 回。
問題:
"abczdetfztfedqzca"
考え方:
文字列の問題はDPの問題と気づきにくい。
この問題の場合、文字列を記憶するメモ化再帰を書くと間に合わない。
まず、文字を加える操作は不要である。
1文字追加することは逆側を削除することに等しい。
次に、文字を書き換える場合に、書き換える文字は気にしなくて良い。
例えば左右で a と b の文字であれば a を b か b を a にすれば良い。
よって a から z への探索などは必要ない。
DPする場合には少ない文字から考えていく。
dp[l][r] が l から r までの文字が、
「回文にするのに必要な操作の数」であるとするとき。
1文字であればすでに回文なので dp[i][i] = 0 である。
また0文字であっても回文とする dp[i+1][i] = 0 でもある。
さて、右に1文字追加するときは必ず1操作が必要である。
逆に左に1文字追加する場合も1操作が必要である。
両側に同じ数字を追加するとき同じ数字であれば0操作、
同じ数字で無ければ1操作が必要である。
少ない文字から問題文の文字列 s になるまで広げていく。
よって、s[l] == s[r] であれば
dp[l][r] = min(dp[l+1][r-1],min(dp[l+1][r]+1,dp[l][r-1]+1));
s[l] != s[r] であれば
dp[l][r] = min(dp[l+1][r-1]+1,min(dp[l+1][r]+1,dp[l][r-1]+1));
という更新をしていけば良い。
答えは dp[0][s.size()-1] に入っている。
string s = "abczdetfztfedqzca";
int n = s.size();
vector<vector<int> > dp(n, vector<int>(n, 0));
for(int i = 1; i < n; i++){
for(int j = 0; j < n - i; j++){
int l = j;
int r = j + i;
if(s[l] == s[r]){
dp[l][r] = dp[l + 1][r - 1];
}
else{
dp[l][r] = dp[l + 1][r - 1] + 1;
}
dp[l][r] = min(dp[l][r], dp[l + 1][r] + 1);
dp[l][r] = min(dp[l][r], dp[l][r - 1] + 1);
}
}
cout << dp[0][n - 1] << endl;
13、制限時間にたくさん到達
問題文:
2次元空間(X方向に最大50、Y方向に最大50)がある。
空間は四角形であって外には出れない。
空間には スタート S(1つ)とゴール G(1つ)がある。
また、他に P 地点(最大 16 個)も存在する。
何も無い歩ける地点は . で表示される。
空間の移動はXかY方向に時間1で1つ進める。
制限時間 T (最大10億)が与えられるので、
制限時間以内にできるだけたくさんの P 地点にたどり着きたい。
ただし、以下のような条件がある。
ひとつの P 地点に着くたびにかかる時間が1加算される。
1つめの P 地点には1つの移動に時間1だが、
2つ目の P 地点までは1つの移動に時間2かかる。
3つめの P 地点までは1つの移動に時間3かかる。
以降も続けて加算されていく。
この条件で制限時間以内に最大いくつの P 地点にたどりつけるか?
例題1:
制限時間:6
S...
....
..PG
であれば S から P 地点まで時間4かかり、
P 地点から G までは時間2かかる。
結局、S から G まで時間6かかるので制限時間に間に合う。
P 地点には1つ到着できるので答えは 1 になる。
例題2:
制限時間:6
S...
..P.
...G
であれば S から P 地点まで時間3かかり、
P 地点から G までは時間4かかる。
S から G まで時間7かかるので制限時間に間に合わない。
この場合 P 地点に到着することはできない。
よって、答えは 0 になる。
例題3:
制限時間:11
S..GPP
このとき G は到着せず通りすぎることができる。
これは S や P 地点についても同じ。
右の P 地点を先に訪れ、左の P 地点に後で到着すれば、
時間10で G に到着できる。
このとき2つの P 地点に着けるので答えは 2 である。
例題4:
制限時間:2
S..GPP
G 地点にたどり着けない場合も答えは 0 になる。
問題:
制限時間:50
.....P
.S.P..
......
.P.P..
P..GP.
......
..P...
考え方:
まずすべての S、P、G の間の距離をすべて求める必要がある。
次の問題はどの P 地点を選択するか?とその順番である。
どの地点にすでに到達したか?という情報は最低限必要なので、
到達済みの地点をビットで記録していくことにする。
また、過去の地点情報だけでは次の地点までの距離が算出できない。
よって、現在どこにいるかも記録していく必要がある。
ゆえに P 地点が n 個あれば dp[1 << n][n] のメモになる。
ここで大事なのはビットの更新の順番になる。
ビットDPで2つめのビットを調べるときには、
ビット1つの情報がすべて埋まっている必要がある。
3つめの地点のときビット2つの情報がすべて必要になる。
よって、この場合のビットDPは、
ビットが1個のとき→2個のとき→3個のとき→4個のとき→、
という順番でまわしていかなければならない。
ビットの更新の順番に工夫がいる。
#define H 7
#define W 6
#define T 50
string d[H] = {
".....P",
".S.P..",
"......",
".P.P..",
"P..GP.",
"......",
"..P..."
};
int n = 0;
pair<int, int> s;
vector<pair<int, int> > p;
pair<int, int> g;
for(int y = 0; y < H; y++){
for(int x = 0; x < W; x++){
if(d[y][x] == 'S'){
s.first = y;
s.second = x;
}
if(d[y][x] == 'P'){
n++;
p.push_back(make_pair(y, x));
}
if(d[y][x] == 'G'){
g.first = y;
g.second = x;
}
}
}
vector<int> sp(n);
vector<vector<int> > pp(n, vector<int>(n));
vector<int> pg(n);
for(int i = 0; i < n; i++){
sp[i] = abs(s.first - p[i].first) + abs(s.second - p[i].second);
}
for(int i = 0; i < n; i++){
pp[i][i] = 0;
for(int j = i + 1; j < n; j++){
pp[i][j] = abs(p[i].first - p[j].first) + abs(p[i].second - p[j].second);
pp[j][i] = pp[i][j];
}
}
for(int i = 0; i < n; i++){
pg[i] = abs(g.first - p[i].first) + abs(g.second - p[i].second);
}
vector<vector<int> > dp(1 << n, vector<int>(n, 1000000));
for(int i = 0; i < n; i++){
dp[1 << i][i] = sp[i];
}
for(int i = 1; i <= n; i++){
vector<int> v;
for(int r = 0; r < n; r++){
if(r < n - i){
v.push_back(0);
}
else{
v.push_back(1);
}
}
do{
int b = 0;
for(int r = 0; r < n; r++){
b |= v[r] << r;
}
for(int r = 0; r < n; r++){
for(int t = 0; t < n; t++){
dp[b | (1 << t)][t] = min(dp[b | (1 << t)][t], dp[b][r] + pp[t][r] * (i + 1));
}
}
}while(next_permutation(v.begin(), v.end()));
}
int mx = 0;
for(int i = 0; i < (1 << n); i++){
int b = 0;
for(int r = 0; r < n; r++){
if(((i >> r) & 1) == 1){
b++;
}
}
for(int r = 0; r < n; r++){
if(dp[i][r] + pg[r] * (1 + b) <= T){
mx = max(mx, b);
}
}
}
cout << mx << endl;