解いた後気づいたけど、Div1 Mediumがこれより制限が強い版だった。
Div1 Mediumやればよかったな。
http://community.topcoder.com/stat?c=problem_statement&pm=11510
問題
店に1つの商品がある。
1日の間に2人客が来る見込があるため、どちらかに商品を売りたい。
2人は1日1回しか来ず、何時に来るかそれぞれ確率が与えられる。また、各時間帯で払う金額が異なる。
また、2人が同時に来ることはない。
2人の客が来る時間・確率・払う金額が与えられるとき、店が最適な客に商品を売る場合、売り上げの期待値を答えよ。
解法
1人目が店に来た後に2人目が来た場合、もう2人目に売るしか選択肢はない。
よって、1人目が店に来た段階で、その後2人目の売り上げ期待値と、その場で1人目に売る場合の期待値のうち大きい方を取ればよい。
なお、Div2 Hardは「2人のうち1人に売る」だが、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はややこしそう。