☆ナップサック(diverta 2019 Programming Contest 2D - Squirrel Merchant)

まだ500が全部埋まったわけではないんですが、典型問題っぽい600が解けるとうれしいなあみたいな気持ちになったりすることが多い（500以下は発想問題であることも多い）ので、コンテスト中に糸口はつかめていたものの解ききれなかった問題を中心に600もたまに解いていこうと思います。

解法

巣->A(1)->B->A(2)->巣と行くので、ドングリの数を増やすために行う動作としては
(a)A(1)で金に変える
(b)Bで金に変える
(c)Bでドングリに変える
(d)A(2)でドングリに変える
の4通りがある。ここで、(b)(c)の順序は自由に組み合わせて入れ替えられるが、それ以外はこの順で行われる。
金属（金g、銀s、銅b）一つに対するドングリのレートが

• Bの方が高い時、(a)(c)を行うとドングリが増える。この時まだBにいるので(b)(d)を行なってもいいはずだが、Bの方がレートが高いので損をするから結局行わない。
• Aの方が高い時、(b)(d)を行うとドングリが増える。この時(a)(c)はこの金属に対して行なっても意味がないのでしない。
• A=Bの時、操作をしてもしなくても変わらない。

結局、(a)(c)を全て行なった後に(b)(d)を全て行った時、(b)(c)を入れ替えた全ての操作方法に対して損をしていないため
、そのような時のみ考えれば良い。

5000個をそのまま金、銀、銅について操作するグループに分けると計算量が大きい。

これは総数Nと、（ドングリ<->金銀銅間で）a個交換すればb個増えるということがわかっているためナップサック問題：

容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題

なので、動的計画法を用いれば良いような気がする。ナップサック問題の計算量はO(Cn)。

しかし注意しないといけないのは、(a)(c)を行なった後ドングリの総数が増えた状態で(b)(d)を行うことができる。先ほど示したように(a)(c)の後に(b)(d)を行なったと考えていいので、単純に前半と後半について分けてナップサック問題を解けば良い。
後半に存在するドングリの数をMとすると計算量はO(3M)なので、O(N*(max(g_x,s_x,b_x)より小さい数))くらいで計算できる。

コード

配列を用意していたのが小さくて配列外参照しているというミスや、初期化に失敗していたためAtCoder上でREになることを直すのに大変時間がかかった。（実装が下手）

同じものをなんども選んでいいナップサック問題に汎用的に使える部分

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back


struct Napsack_multiok{
    int C;
    int N;
    pair<int,int> *prods;
    int *dp;
    int prod_count; 
    Napsack_multiok(int c,int n){
      	C=c;N=n;
        prods = new pair<int,int>[N];
        prod_count=0;
        dp = new int[(C+2)*(N+2)];
      	initdp();
    }
    int mkitr(int x,int y){
        return x*(C+1)+y;
    }
    void initdp(){
        rep(i,N+1){
            rep(j,C+1){
                dp[mkitr(i,j)]=0;
            }
        }
    }
    void push_prods(int c,int p){
        prods[prod_count++]=mp(c,p);
    }
    int solve(){
        initdp();
        rep(i,N+1){
            if(i>0)rep(j,C+1){
                dp[mkitr(i,j)]=dp[mkitr(i-1,j)];
                if(j>0)dp[mkitr(i,j)]=max(dp[mkitr(i,j)],dp[mkitr(i,j-1)]);
                int p=prods[i-1].second;int c=prods[i-1].first;
                if(j-c>=0)dp[mkitr(i,j)]=max(dp[mkitr(i,j)],dp[mkitr(i,j-c)]+p);
            }
        }
        return dp[mkitr(N,C)];
    }
    void debug_printdp(){
        rep(i,N+1){
            rep(j,C+1){printf("%lld ",dp[mkitr(i,j)]);}
            printf("\n");
        }
    }
    void free_(){
        delete[] prods;
        delete[] dp;
    }
    
};

以下本編

int N_input;
int ga,sa,ba,gb,sb,bb;
int ans=0;
signed main(){
    scanf("%lld",&N_input);
    scanf("%lld %lld %lld",&ga,&sa,&ba);
    scanf("%lld %lld %lld",&gb,&sb,&bb);
    Napsack_multiok AC(N_input,3);
    AC.push_prods(ga,gb-ga);AC.push_prods(sa,sb-sa);AC.push_prods(ba,bb-ba);
    int M=AC.solve()+N_input;
    AC.free_();
    Napsack_multiok BD(M,3);
    BD.push_prods(gb,ga-gb);BD.push_prods(sb,sa-sb);BD.push_prods(bb,ba-bb);
  	ans=BD.solve()+M;
    printf("%lld\n",ans);
    BD.free_();
}