torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

M-SOLUTIONS プロコンオープン 2020, D : Road to Millionaire

問題概要

 今,今後 $N$ 日間の株価が分かっていて,$i$ 日目の株価は $A_i$ 円である.$i$ 日目には,以下の行動を(所持金や所持株の範囲内で)何度でも行うことができる.

  • $A_i$ を払って $1$ 株を得る
  • $1$ 株を売って $A_i$ を得る

 最終的に獲得できる金額の最大値はいくらか?

制約

  • $1 \leq N \leq 80$
  • $100 \leq A_i \leq 200$

解法

 まず,ちょっとよく考えると,同日に売りと買いの両方を行うことは無駄です.また,同日での売りまたは買いを $1$ 回ずつ繰り返して行う操作は,まとめて何回か売る or 買う操作として考えても大丈夫なので,そのように考えることとします.
 更に,売り・買いは交互に行うことが最適です.というのも,売り(resp. 買い)を買い(resp. 売り)を挟まずに複数回に分けるならば,より株価が安い(resp. 高い)日にまとめて行った方が得になるからです.また,売りや買いを行って得になるならば,所持している金や株の許す範囲で目一杯やった方が得が大きくなります.よって,最適な戦略とは,最大限の売りと最大限の買いを繰り返す戦略となります.
 以上を踏まえて解法を考えます.安い日に買って高い日に売るような貪欲的な戦略も考えられますが,そういうのは難しいのでここでは DP をします.DP テーブルを以下のように定義します.

  • $\mathit{ dp }_i := i$ 日目の開始時の所持金の最大値

ここで,$i + 1$ 日目に至る手順は,$j$ ($j < i$) 日目を起点として $k$ ($j \leq k < i $) 日目に買って $i$ 日目に売るという形になります.よって,この $j, k$ を全通り試すことで $\mathit{ dp }_{ i + 1 }$ を計算できます.更新が終わった後,$\max \mathit{ dp }$ が答えとなります.
 この DP は,$i, j, k$ を $\leq N$ ぐらいの範囲で全部試すので,$O( N^3 )$ 時間で実行できます.

コード

int main()
{
	IN( int, N );
	VI A( N );
	cin >> A;

	VT< LL > maxs( N + 1 );
	maxs[0] = 1000;

	REP( i, 1, N )
	{
		REP( j, i )
		{
			REP( k, j, i )
			{
				const LL d = maxs[j] / A[k];
				chmax< LL >( maxs[ i + 1 ], maxs[j] - d * A[k] + d * A[i] );
			}
		}
	}

	cout << *max_element( ALL( maxs ) ) << endl;

	return 0;
}