diverta 2019 Programming Contest 2 D問題
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;
}
この記事が気に入ったらサポートをしてみませんか?