Loading [MathJax]/extensions/tex2jax.js

ABC104-C All Green

C++, ★★☆☆☆, アルゴリズム, 動的計画法, 競技プログラミング

ABC104-C All Green

ゆきのん
2018年8月23日
No Comments

今回取り上げるのはこの問題

https://beta.atcoder.jp/contests/abc104/tasks/abc104_c

取り掛かりとして,まず与えられる制約を見てみます.そうすると,\(c_{i},G\)は\(100\)の倍数であること,\(D,p_{i}\)は小さいことが分かります.この制約から座圧を行った場合,状態数が高々\(D*(C+10*p_{i})\)程度に限られるため\(DP\)を考えましょう.この問題は個数に制限があるナップサック問題を少し改変したものに帰着することができます.

今回は\(dp\)を以下の様に定めましょう.

\(dp_{i,k}:=100i点の問題までで、100k点を獲得するのに必要な最小解答数 \)

この\(dp\)の遷移を求めましょう.今\(dp_{i,k}\)が求まっているとして\(dp_{i+1,k}\)について考えます.\(100(i+1)\)点の問題を\(j\)問(\(0 \leq j \leq p_{i+1}\))解いたとして更新します.その時\((i+1)*j\)点獲得でき,\(j=p_{i+1}\)の時は追加で\(c_{i+1}\)点貰えます.よって\(dp\)の遷移は以下の様になります.

\(・dp_{i+1,k+(i+1)*j}=min(dp_{i+1,k+(i+1)*j},dp_{i,k}+j) (j \neq p_{i+1})\)
\(・dp_{i+1,k+(i+1)*j+c[i+1]}=min(dp_{i+1,k+(i+1)*j+c[i+1]},dp_{i,k}+j) (j=p_{i+1})\)

この遷移を行った場合の計算量は\(O(DGmax\{p_{i}\})\)程度でちょっと大きいですが処理が簡潔なので間に合うでしょう.また,この問題の答えは\(min\{\)\(dp_{D,k}|G \leq k\)\(\}\)となります.\(dp\)を\(min\)で更新するので配列は大きな数で初期化しておきましょう.

以下は実装例です.

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fs first
  4. #define sc second
  5. #define mp make_pair
  6. #define pb push_back
  7. #define eb emplace_back
  8. #define ALL(A) A.begin(),A.end()
  9. #define RALL(A) A.rbegin(),A.rend()
  10. typedef long long LL;
  11. typedef pair<LL,LL> P;
  12. const LL mod=1e9+7;
  13. const LL LINF=1LL<<62;
  14. const int INF=10000000;
  17. int dp[11][200001];
  20. int main(){
  21. int D,G;
  22. cin >> D >> G;
  23. G/=100;
  24. int p[D],c[D];
  25. for(int i=0;i<D;i++){
  26. cin >> p[i] >> c[i];
  27. c[i]/=100;
  28. }
  29. for(int i=0;i<=D;i++){
  30. for(int j=0;j<200001;j++){
  31. dp[i][j]=INF;
  32. }
  33. }
  34. dp[0][0]=0;
  35. for(int i=0;i<D;i++){
  36. for(int j=0;j<=p[i];j++){
  37. for(int k=0;k<100001;k++){
  38. if(j==p[i]) dp[i+1][k+(i+1)*j+c[i]]=min(dp[i+1][k+(i+1)*j+c[i]],dp[i][k]+j);
  39. else dp[i+1][k+(i+1)*j]=min(dp[i+1][k+(i+1)*j],dp[i][k]+j);
  40. }
  41. }
  42. }
  43. int ans=INF;
  44. for(int k=G;k<200001;k++){
  45. ans=min(ans,dp[D][k]);
  46. }
  47. cout << ans << endl;
  48. return 0;
  49. }
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const int INF=10000000;


int dp[11][200001];


int main(){
    int D,G;
    cin >> D >> G;
    G/=100;
    int p[D],c[D];
    for(int i=0;i<D;i++){
        cin >> p[i] >> c[i];
        c[i]/=100;
    }
    for(int i=0;i<=D;i++){
        for(int j=0;j<200001;j++){
            dp[i][j]=INF;
        }
    }
    dp[0][0]=0;
    for(int i=0;i<D;i++){
        for(int j=0;j<=p[i];j++){
            for(int k=0;k<100001;k++){
                if(j==p[i]) dp[i+1][k+(i+1)*j+c[i]]=min(dp[i+1][k+(i+1)*j+c[i]],dp[i][k]+j);
                else dp[i+1][k+(i+1)*j]=min(dp[i+1][k+(i+1)*j],dp[i][k]+j);
            }
        }
    }
    int ans=INF;
    for(int k=G;k<200001;k++){
        ans=min(ans,dp[D][k]);
    }
    cout << ans << endl;
    return 0;
}

※追記

上記の方法では最悪計算量は\(10^{8}\)となるので\(dp\)の更新を工夫して計算量を減らしてみる.個数を選ぶ段階で\(2\)倍の個数ずつ選んでいくことで\(max\{p_{i}\}\)が\(log(max\{p_{i}\})\)に落ちる.全部解いた場合のみ特別扱いしてあげれば良く,この場合の計算量は\(O(DGlog(max\{p_{i}\}))\)となる.逆順で更新しなければならないことに注意する.

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fs first
  4. #define sc second
  5. #define mp make_pair
  6. #define pb push_back
  7. #define eb emplace_back
  8. #define ALL(A) A.begin(),A.end()
  9. #define RALL(A) A.rbegin(),A.rend()
  10. typedef long long LL;
  11. typedef pair<LL,LL> P;
  12. const LL mod=1e9+7;
  13. const LL LINF=1LL<<62;
  14. const int INF=10000000;
  16. int dp[11][200001];
  18. const int lim=114514;
  20. int main(){
  21. int D,G;
  22. cin >> D >> G;
  23. G/=100;
  24. int p[D],c[D];
  25. for(int i=0;i<D;i++){
  26. cin >> p[i] >> c[i];
  27. c[i]/=100;
  28. }
  29. for(int i=0;i<=D;i++){
  30. for(int j=0;j<200001;j++){
  31. dp[i][j]=INF;
  32. }
  33. }
  34. dp[0][0]=0;
  35. for(int i=0;i<D;i++){
  36. for(int k=0;k<=lim;k++) dp[i+1][k]=dp[i][k];
  37. int tp=p[i]-1;
  38. for(int j=0;tp>0;j++){
  39. int num=min(tp,1<<j);
  40. tp-=num;
  41. for(int k=lim;k>=0;k--){
  42. if(dp[i+1][k]==INF) continue;
  43. dp[i+1][k+(i+1)*num]=min(dp[i+1][k+(i+1)*num],dp[i+1][k]+num);
  44. }
  45. }
  46. for(int k=0;k<lim;k++){
  47. dp[i+1][k+p[i]*(i+1)+c[i]]=min(dp[i+1][k+p[i]*(i+1)+c[i]],dp[i][k]+p[i]);
  48. }
  49. }
  50. int ans=INF;
  51. for(int k=G;k<lim;k++) ans=min(ans,dp[D][k]);
  52. cout << ans << endl;
  53. return 0;
  54. }
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const int INF=10000000;

int dp[11][200001];

const int lim=114514;

int main(){
    int D,G;
    cin >> D >> G;
    G/=100;
    int p[D],c[D];
    for(int i=0;i<D;i++){
        cin >> p[i] >> c[i];
        c[i]/=100;
    }
    for(int i=0;i<=D;i++){
        for(int j=0;j<200001;j++){
            dp[i][j]=INF;
        }
    }
    dp[0][0]=0;
    for(int i=0;i<D;i++){
        for(int k=0;k<=lim;k++) dp[i+1][k]=dp[i][k];
        int tp=p[i]-1;
        for(int j=0;tp>0;j++){
            int num=min(tp,1<<j);
            tp-=num;
            for(int k=lim;k>=0;k--){
                if(dp[i+1][k]==INF) continue;
                dp[i+1][k+(i+1)*num]=min(dp[i+1][k+(i+1)*num],dp[i+1][k]+num);
            }
        }
        for(int k=0;k<lim;k++){
            dp[i+1][k+p[i]*(i+1)+c[i]]=min(dp[i+1][k+p[i]*(i+1)+c[i]],dp[i][k]+p[i]);
        }
    }
    int ans=INF;
    for(int k=G;k<lim;k++) ans=min(ans,dp[D][k]);
    cout << ans << endl;
    return 0;
}

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です