Typical DP Contest A - コンテスト
問題
問題概要
N問の問題があるコンテストがあり、i問目(1-index)の問題の配点は
p[i-1]点である。この問題の中から何問か解き、解いた問題の配点の合計が得点となる。このコンテストの得点は何通り考えられるか。
解法
dp[i][j] : i番目まで見て点数がjになる通り数
0≦i≦N、0≦j≦Σp[i-1]
dp[i][j]=dp[i-1][j]+dp[i-1][j-p[i-1]]
ただしj-p[i-1]<0の時は
dp[i][j]=dp[i-1][j]
i=0かつj=0のとき
dp[i][j]=1
i=0かつj≠0のとき
dp[i][j]=0
答えはi=Nのときのj≠0となる個数
ソースコード
signed main() {
int N;
cin >> N;
vector<int>p(N);
int Sp = 0;
rep(i, N) {
cin >> p[i];
Sp += p[i];
}
vector<vector<int>>dp(N + 1, vector<int>(Sp + 1));
rep(i, N + 1) {
rep(j, Sp + 1) {
if (i == 0 && j == 0) {
dp[i][j] = 1;
}
else if (i == 0 && j != 0) {
dp[i][j] = 0;
}
else if (j - p[i - 1] < 0) {
dp[i][j] = dp[i - 1][j];
}
else {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - p[i - 1]];
}
}
}
int ans = 0;
rep(i, N + 1) {
rep(j, Sp + 1) {
if (i == N) {
ans += dp[i][j] != 0;
}
}
}
cout << ans << endl;
}
WUPC 2012 D - 三角パズル
問題
問題概要
N段の直角三角形状の数列が与えられる。
例)
7
2 3
1 5 4
頂点からスタートして真下もしくは右下に行くことが出来る。底辺までたどり着いたときに経路中の数値の合計の最大値を求めよ。
上の例だと7+3+5=15
解法
上からi番目、左からj番目の数をa[i][j]とする。
dp[i][j] : a[i][j]まで到達したときの経路中の数値の最大値
0≦i≦N-1、0≦j≦i
a[i][j]には上(a[i-1][j])からもしくは左上(a[i-1][j-1])から来るのでそこまでの最大値を持っておけばそこからa[i][j]までの最大値が分かる。
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]
i=0もしくはj=0ときは配列外参照になるので別な処理をする。
(i)i=0かつj=0のとき
dp[i][j]=a[i][j]
(ii)i≠0かつj=0のとき
dp[i][j]=dp[i-1][j]+a[i]
i=j(≠0)のときは左上からしか行けないので
dp[i][j]=dp[i-1][j-1]+a[i][j]
(dp[i-1][j]=0よりmax(dp[i-1][j],dp[i-1][j-1])=dp[i-1][j-1]なのでこの場合分けはなくても大丈夫)
ソースコード
signed main() {
int N;
cin >> N;
vector<vector<int>>a(N, vector<int>(N));
rep(i, N) {
rep(j, i + 1) {
cin >> a[i][j];
}
}
vector<vector<int>>dp(N, vector<int>(N));
rep(i, N) {
rep(j, i + 1) {
if (i == 0 && j == 0) {
dp[i][j] = a[i][j];
}
else if (i != 0 && j == 0) {
dp[i][j] = dp[i - 1][j] + a[i][j];
}
else if (i == j) {
dp[i][j] = dp[i - 1][j - 1] + a[i][j];
}
else {
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
}
}
}
int ans = 0;
rep(i, N) {
rep(j, i + 1) {
if (i == N - 1) {
ans = max(ans, dp[i][j]);
}
}
}
cout << ans << endl;
}
AtCoder Regular Contest 060 C - 高橋君とカード
問題
問題概要
N枚のカードがあり、i番目(1-index)のカードには整数x[i-1]が書かれている。
何枚かカードを選びカードの整数の平均がAとなるようにしたい。そのような選び方は何通りあるか。
解法
平均を平均のまま扱うのは大変なので合計と個数を扱う。
dp[i][j][k] : i番目(1-index)まで見てj枚選び、合計がkである通り数。
0≦i≦N、0≦j≦N、0≦k≦Σx[i-1]
こうすれば答えは
i=Nかつk=j*Aとなるdp[i][j][k]の合計である。(j=0かつk=0の時を除く)
i番目のカードを選ぶか選ばないかの2通りある。
i番目のカードを選ばないとき
dp[i][j][k]=dp[i-1][j][k]
i番目のカードを選ぶとき
dp[i][j][k]=dp[i-1][j-1][k-x[i-1]]
これらの合計となる。
しかしj-1<0またはk-x[i-1]<0の時は配列外参照となるため
dp[i][j][k]=dp[i-1][j][k]
となる。
i=0の時
j=0かつk=0の時はdp[i][j][k]=1
それ以外の時はdp[i][j][k]=0
ソースコード
signed main() {
int N, A;
cin >> N >> A;
vector<int>x(N);
int Sx = 0;
rep(i, N) {
cin >> x[i];
Sx += x[i];
}
vector<vector<vector<int>>>dp(N + 1, vector<vector<int>>(N + 1, vector<int>(Sx + 1)));
rep(i, N + 1) {
rep(j, N + 1) {
rep(k, Sx + 1) {
if (i == 0) {
if (j == 0 && k == 0) {
dp[i][j][k] = 1;
}
else {
dp[i][j][k] = 0;
}
}
else {
if (j - 1 < 0 || k - x[i - 1] < 0) {
dp[i][j][k] = dp[i - 1][j][k];
}
else {
dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i - 1]];
}
}
}
}
}
int ans = 0;
rep(i, N + 1) {
rep(j, N + 1) {
rep(k, Sx + 1) {
if (i == N && k == j * A && j!=0 && k!=0) {
ans += dp[i][j][k];
}
}
}
}
cout << ans << endl;
}
Educational DP Contest I - Coins
問題
問題概要
コインがN枚あり、i番目(1-index)のコインの表が出る確率がp[i-1]、裏が出る確率が1-p[i-1]である。
N枚のコインを投げたとき、表の個数が裏の個数を上回る確率を求めよ。
解法
dp[i][j] : i番目(1-index)のコインまで投げたときに
(表の枚数)-(裏の枚数)=j
となる確率。
0≦i≦N、-N≦j≦N
これだとjが負の数になることがあるので調整する。
dp[i][N+1+j] : i番目(1-index)のコインまで投げたときに
(裏の枚数)-(表の枚数)=j
となる確率。
0≦i≦N、1≦N+1+j≦2*N+1
dp[i][N+1+j]=dp[i-1][N+j]*(1-p[i-1])+dp[i-1][N+2+j]*p[i-1]
i=0かつj=0の時はdp[i][N+1+j]=1
i=0かつj≠0の時はdp[i][N+1+j]=0
答えは
i=Nかつj<0の時のdp[i][N+1+j]の総和
ソースコード
signed main() {
int N;
cin >> N;
vector<double>p(N);
rep(i, N) {
cin >> p[i];
}
vector<vector<double>>dp(N + 1, vector<double>(2 * N + 3));
rep(i, N + 1) {
for (int j = (-1) * N; j <= N; j++) {
if (i == 0) {
if (j == 0) {
dp[i][N+1+j] = 1;
}
else {
dp[i][N+1+j] = 0;
}
}
else {
dp[i][N + 1 + j] = dp[i - 1][N + j] * (1 - p[i - 1]) + dp[i - 1][N + 2 + j] * p[i - 1];
}
}
}
double ans = 0;
rep(i, N + 1) {
for (int j = (-1) * N; j <= N; j++) {
if (i == N && j < 0) {
ans += dp[i][N + 1 + j];
}
}
}
cout << fixed << setprecision(20) << ans << endl;
}
コメント
dp[i][j] : i枚目のコインまで投げたとき、表がj枚でる確率
にした方が簡単だった。
AtCoder Beginner Contest 054 D - Mixing Experiment
問題
問題概要
薬品がN個あり、i個目の薬品はタイプAの薬品をa[i-1]グラム、タイプBの薬品をb[i-1]グラム含み、価格はc[i-1]である。
これらの薬品のうちからいくつか選んで混合し、タイプAとタイプBの薬品の混合比がMa:Mbとなるようにしたときの最小予算を求めよ。
解法
ナップサックdpに似ている。
dp[i][j][k] : i番目(1-index)の薬品まで見てタイプAがjグラム、タイプBがkグラム混合されるようにしたときの最小予算。
0≦i≦N、0≦j≦Σa[i]、0≦k≦Σb[i]
今回は「～以内」ではなく「ちょうど～」なのでそのような組み合わせが存在しないことがある。この時のことも考えなくてはいけないため場合分けが多くなる。
最小値を求めたいのでdpはINFで初期化する。
dp[i][j][k]=INFの時はi番目まで見てタイプAがjグラム、タイプBがkグラム混合されるように選ぶ方法はないということである。
i番目を混合するか混合しないかの2通りある。
i番目を混合しないとき
dp[i][j][k]=dp[i-1][j][k]
i番目を混合するとき
dp[i][j][k]=dp[i-1][j-a[i-1]][k-b[i-1]]+c[i-1]
これらのうちの小さいほうである
ただしj-a[i-1]<0またはk-b[i-1]<0の時は配列外参照になるため
dp[i][j][k]=dp[i-1][j][k]となる。
また、dp[i-1][j][k]=INFかつdp[i-1][j-a[i-1]][k-b[i-1]]=INFの時は
dp[i][j][k]も作れないのでINFとなる。
i=0の時は
j=0かつk=0の時はdp[i][j][k]=0となり、
それ以外の時は作れないのでdp[i][j][k]=INFとなる。
答えはi=Nでj:k=Ma:Mbとなるdp[i][j][k]のうちの最小値である。
ソースコード
signed main() {
int N, Ma, Mb;
cin >> N >> Ma >> Mb;
vector<int>a(N);
vector<int>b(N);
vector<int>c(N);
rep(i, N) {
cin >> a[i] >> b[i] >> c[i];
}
int Sa = 0;
int Sb = 0;
rep(i, N) {
Sa += a[i];
Sb += b[i];
}
Sa++;
Sb++;
vector<vector<vector<int>>>dp(N + 1, vector<vector<int>>(Sa, vector<int>(Sb,INF)));
rep(i, N + 1) {
rep(j, Sa) {
rep(k, Sb) {
if (i == 0) {
if (j == 0 && k == 0) {
dp[i][j][k] = 0;
}
}
else {
if (j - a[i - 1] < 0 || k - b[i - 1] < 0) {
dp[i][j][k] = dp[i - 1][j][k];
}
else {
if (dp[i - 1][j][k] == INF && dp[i - 1][j - a[i - 1]][k - b[i - 1]] == INF) {
dp[i][j][k] = INF;
}
else {
dp[i][j][k] = min(dp[i - 1][j][k], dp[i - 1][j - a[i - 1]][k - b[i - 1]] + c[i - 1]);
}
}
}
}
}
}
int ans = INF;
rep(i, N + 1) {
rep(j, Sa) {
rep(k, Sb) {
if (i == N && j * Mb == k * Ma &&j!=0&&k!=0) {
ans = min(ans, dp[i][j][k]);
}
}
}
}
if (ans == INF) {
cout << -1 << enld;
}
else {
cout << ans << endl;
}
}
AtCoder Beginner Contest 015 D - 高橋くんの苦悩
問題
問題概要
ナップサック問題に言い換える。
品物がN個ありi番目(1-index)の重さはA[i-1]、価値はB[i-1]である。
重さがWを超えず、個数がKを超えないように選ぶとき、価値の合計の最大値を求めよ。
解法
個数制限がない場合は普通のナップサック問題なので以下の記事の方法で解けばいい。
greentomatotan.hatenadiary.jp
この場合は個数制限があるので添え字を増やす。
dp[i][j][k] : i番目(1-index)の品物まで見て重さがjを超えないように、個数がkを超えないように選ぶときの価値の合計の最大値。
0≦i≦N、0≦j≦W、0≦k≦K
i番目の品物を選ぶか選ばないかの2通りがある。
i番目の品物を選ばないとき
dp[i][j][k]=dp[i-1][j][k]
i番目の品物を選ぶとき
dp[i][j][k]=dp[i-1][j-A[i-1]][k-1]+B[i-1]
これらのうちの大きい方となる。
ただしj-A[i-1]<0またはk-1<0の時は配列外参照となるため
dp[i][j][k]=dp[i-1][j][k]となる。
i=0の時は何も選ばないのでdp[i][j][k]=0となる。
ソースコード
signed main() {
int W, N, K;
cin >> W >> N >> K;
vector<int>A(N);
vector<int>B(N);
rep(i, N) {
cin >> A[i] >> B[i];
}
vector<vector<vector<int>>>dp(N + 1, vector<vector<int>>(W + 1, vector<int>(K + 1)));
rep(i, N + 1) {
rep(j, W + 1) {
rep(k, K + 1) {
if (i == 0) {
dp[i][j][k] = 0;
}
else {
if (j - A[i - 1] < 0 || k - 1 < 0) {
dp[i][j][k] = dp[i - 1][j][k];
}
else {
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - A[i - 1]][k - 1] + B[i - 1]);
}
}
}
}
}
cout << dp[N][W][K] << endl;
}
Educational DP Contest D - Knapsack 1
問題
問題概要
N個の品物があり、i番目(1-index)の品物の品物の重さはw[i-1]で、価値はv[i-1]である。
品物を重さの合計がWを超えないように選ぶとき価値の総和の最大値を求めよ。
解法
ナップサックDPである。
dp[i][j] : i番目まで見て重さの合計がjを超えないように選んだときの価値の合計の最大値
0≦i≦N , 0≦j≦W
i番目の品物を選ぶか選ばないかの2通りがある。
i番目の品物を選ばないとき
dp[i][j]=dp[i-1][j]
i番目の品物を選ぶとき
dp[i][j]=dp[i-1][j-w[i-1]]+v[i-1]
dp[i][j]はこれらのうち大きいほうである。
しかしj-w[j-1]<0の時は配列外参照になるので
dp[i][j]=dp[i-1][j]
になる。
i=0の時は何も選んでいないのでdp[i][j]は0になる。
ソースコード
signed main() {
int N, W;
cin >> N >> W;
vector<int>w(N);
vector<int>v(N);
rep(i, N) {
cin >> w[i] >> v[i];
}
vector<vector<int>>dp(N + 1, vector<int>(W + 1));
rep(i, N + 1) {
rep(j, W + 1) {
if (i == 0) {
dp[i][j] == 0;
}
else {
if (j - w[i - 1] < 0) {
dp[i][j] = dp[i - 1][j];
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
}
}
cout << dp[N][W] << endl;
}
