2019年6月15日開催のdiverta 2019 Programming Contest 2 に参加した．B問題の私の理解と解説．コンテスト 中では問題文を読んだだけで終わってしまた．

D - Squirrel Merchant

問題文はこちら．ドングリと金属(金，銀，銅)の交換を繰り返し，最終的なドングリの数を最大にする問題．

取引前と全取引後はドングリしか持ち得ないので，各取引所での交換パターンは

初回A: 所持しているドングリN個のうち，いくつかを金属に換える
B　:　所持しているドングリをいくつか金属に，金属をドングリに換える．
2回目A: 所持している金属を全てドングリに換える

初回のAを取引A1，2回目のAを取引A2と呼ぶことにする．取引の順番は自由なので，Bでの取引のうち，「金属をドングリに換える」を取引B1，「ドングリを金属に換える」を取引B2．と呼ぶことにし，
A1 → B1 → B2 → A2 
の順で取引を進めることにする．まず，前半のA1，B1の取引が終わった時点でのドングリ数を最大にし，それを元手に後半のB2，A2を行いドングリを最大にする．A1，B1の取引で，余計な取引を行なっていてもB2，A2でもとに戻せるので前半は単独で最大化しておいてよい．

前半A1，B1終了時のドングリ最大化

A1，B1のあとドングリ数を最大にするためには，A1で得た金属は全てB1でドングリになっている．そのため，A1での「ドングリ→ある金属」とB1での「ある金属→ドングリ」は1セットと考えてよい．これを取引セットと呼ぶことにする．
取引の一例：

前半A1，B1終了時のドングリ最大値は，動的計画法(DP)で求める．dp[k]を取引前のドングリ数k個から初めたときの前半A1，B1終了時の最大ドングリ数とする．

まず，dp[k]をdp[k-1], dp[k-2], ... , dp[0]で書いた漸化式を求める．
仮に，最初の手持ちがドングリk個のとき，dp[k]に至る前半最後の取引セットが金を介した取引のとき，dp[k] = dp[k-gA] + gB と書ける．
右辺第二項 gB は最後の取引セットのB1で得るドングリの数で，第一項は最後の取引セットで使用しない k-gA 個のドングリを元手に得られるドングリの最大値である．

さて，最後の取引セットが金を介すもの以外にも，銀，銅を介すもの，あるいは取引しない場合も考えられるので，dp[k]は

dp[k] = max(dp[k-gA] + gB, dp[k-sA] + sB, dp[k-bA] + bB, dp[k-1]+1)

となる．

後半B2，A2終了時のドングリ最大化

後半は，前半のNをdp[N]に，gA, sA, bAをgB, sB, bB に置き換えて同じことをすれば良い．

実装例

C++での実装例は以下(#include は省略)．実装の際は，k(下のコードではi) が金属に交換可能な個数に達しているか判定する必要もある．また，ドングリの個数は入力次第で前半取引後 5000^2 個，後半取引後 5000^3 個に達するので，後半はintに収まりきれないことに注意する．

using namespace std;

int main() {
 int N, ga, sa, ba, gb, sb, bb;
 cin >> N;
 cin >> ga >> sa >> ba >> gb >> sb >> bb;
 vector<long long> dp1, dp2;
 
 // A1, B1 後の最大ドングリ数を求める．
 dp1.push_back(0); // dp1[0] = 0;
 for(int i=1; i<N+1; i++) {
   long long dg=0, ds=0, db=0;
   if(i>=ga) dg = dp1[i-ga] + gb;
   if(i>=sa) ds = dp1[i-sa] + sb;
   if(i>=ba) db = dp1[i-ba] + bb;
   long long dd = dp1[i-1] + 1;
   dp1.push_back(max(max(dd, dg), max(ds, db)));
 }
 
 //cout << dp1[N] << endl;
 
 // B2, A2 後の最大ドングリ数を求める．
 dp2.push_back(0); // dp2[0] = 0;
 for(int i=1; i<dp1[N]+1; i++) {
   long long dg=0, ds=0, db=0;
   if(i>=gb) dg = dp2[i-gb] + ga;
   if(i>=sb) ds = dp2[i-sb] + sa;
   if(i>=bb) db = dp2[i-bb] + ba;
   long long dd = dp2[i-1] + 1;
   dp2.push_back(max(max(dd, dg), max(ds, db)));
 }
 
 cout << dp2[dp1[N]] << endl;
 
 return 0;
}