TopCoder SRM 515 Div2 Hard NewItemShopTwo

解いた後気づいたけど、Div1 Mediumがこれより制限が強い版だった。
Div1 Mediumやればよかったな。
http://community.topcoder.com/stat?c=problem_statement&pm=11510

問題

店に１つの商品がある。
１日の間に２人客が来る見込があるため、どちらかに商品を売りたい。

２人は１日１回しか来ず、何時に来るかそれぞれ確率が与えられる。また、各時間帯で払う金額が異なる。
また、２人が同時に来ることはない。
２人の客が来る時間・確率・払う金額が与えられるとき、店が最適な客に商品を売る場合、売り上げの期待値を答えよ。

解法

１人目が店に来た後に２人目が来た場合、もう２人目に売るしか選択肢はない。
よって、１人目が店に来た段階で、その後２人目の売り上げ期待値と、その場で１人目に売る場合の期待値のうち大きい方を取ればよい。

なお、Div2 Hardは「２人のうち１人に売る」だが、Div1 Mediumは「N人のうちM人に売る」とさらにややこしくなっている。

int N[2];
int T[2][51],C[2][51],P[2][51];


class NewItemShopTwo {
	public:
	double getMaximum(vector <string> customers) {
		int i,j,x,y;
		string s;
		ZERO(T),ZERO(C),ZERO(P);
		FOR(i,2) {
			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) P[i][N[i]]=P[i][N[i]]*10+*it-'0';
			}
			N[i]++;
		}
		double r=0;
		FOR(i,2) {
			int lx=100;
			FOR(x,N[i]) {
				int ly=100;
				double expe=0;
				FOR(y,N[i^1]) {
					if(T[i^1][y]<T[i][x]) ly-=P[i^1][y];
					else expe+=C[i^1][y]*P[i^1][y];
				}
				
				r += max((double)C[i][x],ly?(expe/ly):0)*P[i][x]*ly/10000.0;
				lx-=P[i][x];
			}
			
		}
		
		return r;
	}
};

まとめ

Div2 Hardは易しいけど、Div1 Mediumはややこしそう。