yukicoder : No.1590 Random Shopping

これはすんなり思いついてよかった。
https://yukicoder.me/problems/no/1590

問題

店では今後N日間にわたり物が売られる。
i日目朝には、A[i]円の商品が店に追加され、以後売り切れるまでその商品はずっと店に残る。
i日目には、裕福さR[i]の人が店に来る。そして50%の確率で、店にある最安の商品を1つ買い、残り50%では何もしない。

(裕福さ×購入金額)のN日間の総和の期待値を求めよ。

解法

まず商品を金額順にソートしよう。
その後、商品毎にその商品が何日目に売れるかDPで求める。
状態としては、日付と、対象の商品より安いものが何個店に並んでいるかを持てばよく、O(N^3)で解ける。

int N;
int A[505];
int R[505];
pair<int,int> P[1010];
int O[505];

double from[505];
double to[505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) {
		cin>>R[i];
		P[i]={A[i],i};
	}
	sort(P,P+N);
	FOR(i,N) O[P[i].second]=i;
	
	double ret=0;
	FOR(x,N) {
		ZERO(from);
		from[0]=1;
		FOR(y,N) {
			ZERO(to);
			
			if(O[y]<=O[x]) {
				for(k=N;k>=0;k--) from[k+1]=from[k];
				from[0]=0;
			}
			
			FOR(k,y+2) {
				to[k]+=from[k]/2.0;
				if(y>=x&&k==1) {
					ret+=from[k]/2.0*A[x]*R[y];
				}
				else {
					to[max(0,k-1)]+=from[k]/2.0;
				}
			}
			swap(from,to);
		}
	}
	_P("%.12lf\n",ret);
	
}

まとめ

実装も重くないし、★3.5でもいいかもしれない。