kmjp's blog

競技プログラミング参加記です

TopCoder SRM 515 Div1 Medium NewItemShop

SRM

先日Div2 Hardを解いたので、その制限が難しい版。
http://community.topcoder.com/stat?c=problem_statement&pm=11508

問題

下記Div2 Hardを参照。
TopCoder SRM 515 Div2 Hard NewItemShopTwo - kmjp's blog

ただし、Div2 HardとDiv1 Mediumは以下の点が異なる。

  • Div2 Hardは客は２人だが、こちらは客は最大24人である。
  • Div2 Hardは売るものは１つしかないが、こちらはsword個ある。

それぞれの客が最大１回しか店に来ない場合、利益を最大化せよ。

解法

基本的な解法はDiv2 Hardと変わらない。
ただ、自分でさらっと再帰が書けなかったので一部他の解答を参考にした。

後ろの時間から順に、「残された客が来る確率」をもとにその時間に来た客にものを売るか売らないか最適手を取っていく。


ただし、test #0のように8時または16時に来る客がいる場合、12時の客の相手をどうするかは８時にすでに客が来たかどうかで決まる。
そこで、状態として[時間][残りsword数][以前に客が来たかのbitmap]を持つ。
客の数は最大24人いるが、bitmaskを持たなければいけないのは、２回以上来る客だけなので、最大12bitで良い。

あとは以下の処理を0時から再帰的に行う。結果的に後ろの時刻から最適手が確定していく。

  • 今の時間に客が来ないなら、次の時間の結果を返す。
  • bitmaskを見て、今の時間の客が来ないのが確定的(前の時間にすでに来ている)なら、次の時間の結果を返す。
    • それ以外の場合は、今の状態の最大利益を書き手順で求める。
    • まず、この時間に客が来る確率を求める。その確率は、(今客が来る確率)/(これまでにその客が来ない確率)である。
    • 客が来る場合、商品を売るか売らないか最大値を選択する。その際、この時間客が来るので以降bitmaskのビットを立てて処理する。
      • 売る場合、その分の利益と、残りの時間で１つ少ない商品で得られる利益を再帰的に求める。
      • 売らない場合、残りの時間で得られる利益を再帰的に求める。
    • 来る場合の利益と来ない場合の利益とそれぞれの確率から、期待値を求める。
int CC,NB;
int N[51];
int B[51];
int T[51][51],C[51][51],IP[51][51];
double P[51][51],TP[51][51];

double dpdp[25][25][1<<12];
int TN[51],TID[51];

class NewItemShop {
	public:
	
	double dodo(int tim, int sw, int mask) {
		
		if(tim>=24 || sw<=0) return 0;
		if(dpdp[tim][sw][mask]>=0) return dpdp[tim][sw][mask];
		
		if(TN[tim]==-1) return dpdp[tim][sw][mask] = dodo(tim+1, sw, mask);
		if(B[TN[tim]]>=0 && (mask & (1<<B[TN[tim]]))) return dpdp[tim][sw][mask] = dodo(tim+1, sw, mask); 
		
		double happen=P[TN[tim]][TID[tim]]/(1-TP[TN[tim]][tim]);
		
		double ntp = dodo(tim+1, sw, mask);
		int nm=mask;
		if(B[TN[tim]]>=0) nm |= 1<<B[TN[tim]];
		double take = 0;
		if(sw>0) take = C[TN[tim]][TID[tim]] + dodo(tim+1,sw-1,nm);
		double notake = dodo(tim+1,sw,nm);
		
		return dpdp[tim][sw][mask] = happen*max(take,notake) + (1-happen)*ntp;
		
		
	}
	
	double getMaximum(int swords, vector <string> customers) {
		int i,j,x,y,t;
		string s;
		
		CC=customers.size();
		NB=0;
		ZERO(N);MINUS(B);
		ZERO(T);ZERO(C);ZERO(P);ZERO(IP);
		MINUS(TN),MINUS(TID);ZERO(TP);
		FOR(i,CC) {
			int d=0,j;
			N[i]=0;
			
			ITR(it,customers[i]) {
				if(*it==',') d++;
				else if(*it==' ') d=0,N[i]++;
				else if(d==0) T[i][N[i]]=T[i][N[i]]*10+*it-'0';
				else if(d==1) C[i][N[i]]=C[i][N[i]]*10+*it-'0';
				else if(d==2) IP[i][N[i]]=IP[i][N[i]]*10+*it-'0';
			}
			N[i]++;
			FOR(j,N[i]) TN[T[i][j]]=i,TID[T[i][j]]=j,P[i][j]=IP[i][j]/100.0;
			FOR(j,N[i]) for(x=T[i][j]+1;x<=24;x++) TP[i][x] += P[i][j];
			if(N[i]>1) B[i]=NB++;
		}
		
		FOR(i,25) FOR(j,25) FOR(x,1<<12) dpdp[i][j][x]=-1;
		return dodo(0,swords,0);
	}
};

まとめ

わかりやすい問題設定だが、地味に面倒だ。