Educational DP Contest を解く - 頭良くなりたい人

どうも，『アルゴリズム理論の基礎』でアルゴリズムを初めて勉強しているshadeです。まだ読了できていませんが，競技プログラミングでは頻出（多分）の動的計画法（DP）について一通り勉強したので，アウトプットも兼ねてAtCoderの「Educational DP Contest / DP まとめコンテスト」の問題を解いていきたいと思います。

順次解いた問題は追加されます。

コンテストページはこちら atcoder.jp

A - Frog1

方針

足場 $1$ から足場 $i$ に辿り着くまでのコストの総和の最小値を $m(i)$ ，足場 $i-1$ から足場 $i$ に行くためのコストを $a(i)$ ，足場 $i-2$ から足場 $i$ に行くためのコストを $b(i)$ と表すと， $a(i)=|h_{i-1}-h_i|,b(i)=|h_{i-2}-h_i|$ であり，足場 $i$ の直前は足場 $i-1$ ， $i-2$ のいずれかであるから，一般に，

です。 $i$ の値を増加させながらこれを計算し， $m(N)$ を求めます。

コード

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    cin>>n;
 
    vector<int> h(n);
    for(int i=0; i<n; i++){
        cin>>h[i];
    }
 
    vector<int> m(n),a(n),b(n);
    a[0]=0,b[0]=0,m[0]=0;
    a[1]=abs(h[0]-h[1]),b[1]=0,m[1]=a[1];
 
    for(int i=2; i<n; i++){
        a[i]=abs(h[i-1]-h[i]);
        b[i]=abs(h[i-2]-h[i]);
        m[i]=min(m[i-1]+a[i],m[i-2]+b[i]);
    }
 
    cout<<m[n-1]<<endl;    
}

C - Vacation

方針

$i$ 日目までの幸福度の総和の最大値を $M(i)$ とします。ここで， $i$ 日目までの幸福度の総和について， $i$ 日目にA,B,Cを選んだ場合の最大値をそれぞれ $X(i),Y(i),Z(i)$ とすると，明らかに， $M(i)=\max$ { $X(i),Y(i),Z(i)$ } です。さらに，2日連続で同じ選択はできないので， $i-1$ 日目には $i$ 日目とは異なる選択をしています。つまり，

です。この計算を繰り返して $M(N)$ を求めます。

コード

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    
    vector<int> a(n),b(n),c(n);
    for(int i=0; i<n; i++){
        cin>>a[i]>>b[i]>>c[i];
    }
 
    vector<int> x(n),y(n),z(n);
    x[0]=a[0],y[0]=b[0],z[0]=c[0];
 
    for(int i=1; i<n; i++){
        x[i]=max(y[i-1],z[i-1])+a[i];
        y[i]=max(z[i-1],x[i-1])+b[i];
        z[i]=max(x[i-1],y[i-1])+c[i];
    }
    
    cout<<max(max(x[n-1],y[n-1]),z[n-1])<<endl;
}

D - Knapsack1

方針

ナップサックの容量を $i$ ，品物を $1,2,...,j$ としたとき，持ち帰る品物の価値の総和の最大値を $M(i,j)$ とします。(i)品物 $j$ を選ばないとき，価値の総和の最大値は，品物が $1,2,...,j-1$ である場合の最大値と等しく，(ii)品物 $j$ を選ぶとき，価値の総和の最大値は，ナップサックの容量が $i-w_j$ （品物 $j$ の分を開けておく），品物が $1,2,...,j-1$ である場合の最大値に $v_j$ を加えたものに等しいので，

と表せます。 $i - w_j$ は負にはなれないので注意が必要です。求める最大値は， $M(W,N)$ です。

コード

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,W;
    cin>>n>>W;

    vector<int> w(n),v(n);
    for(int i=0; i<n; i++){
        cin>>w[i]>>v[i];
    }

    vector<vector<long>> M(W,vector<long>(n));
    for(int i=0; i<W; i++){
        if(i+1>=w[0]){
            M[i][0]=v[0];
        }else{
            M[i][0]=0;
        }
    }    
    
    for(int i=0; i<W; i++){
        for(int j=1; j<n; j++){
            if(i-w[j]<0){
                M[i][j]=M[i][j-1];
            }else{
                M[i][j]=max(M[i][j-1],M[i-w[j]][j-1]+v[j]);
            }
        }
    }

    cout<<M[W-1][n-1]<<endl;
}