TopCoder SRM 642 Div1 Hard WheelofFortune

時間かかったけど自力で解けた。800ptだしね。
http://community.topcoder.com/stat?c=problem_statement&pm=13502

問題

N個のセクタに分かれた円形の車輪を使ってゲームを行う。
各セクタのスコアは初期状態で0である。

この車輪に対し、M回スコアの追加を行う。
各追加はパラメータs[i]で表される。
これは、車輪のうち等確率でランダムにどこか連続したs[i]個のセクタのスコアを1ポイントインクリメントする。

この状態の車輪に対し、プレイヤーは２つのセクタを選択すると、そのスコアの合計が取得スコアとなる。
スコア追加後の各セクタのスコアはプレイヤーには伝えられない。
ただし１つ目のセクタを選択すると、そのセクタのスコアを教えて貰うことができるので、その情報を参考に２つ目のセクタを選択できる。

プレイヤーが最適手を取る場合、プレイヤーの取得スコアの期待値を求めよ。

解法

１手目は何も情報がないので、どこのセクタを選択しても取得するスコアの期待値は同じである。
１回のスコア追加あたりs[i]/Nの確率で１ポイント得られる単純なDPで計算できる。

問題は１手目の情報をもとに２手目をどう選択するかである。
結論としては、状態として[２手目の位置][１手目のポイント]を持ち、２手目のポイントの期待値をDPで求めていけば良い。
２手目の各位置について、１手目をs[i]/Nの確率でポイントを得た場合と、(N-s[i])/Nの確率でポイントを得られなかった場合それぞれ、２手目でポイントを得られるかどうかを求め、重みづけ平均を求めていく。

あとは最後に、１手目の取得ポイント数ごとに、２手目の期待値が最高となる２手目の位置を選択して合計の期待値を求めていけば良い。

class WheelofFortune {
	public:
	double maxExpectedValue(int N, vector <int> s) {
		int i,x,y;
		int L=s.size();
		double dp[303]={},op[2][303][303];
		
		ZERO(op);
		dp[0]=1;
		
		FOR(i,L) {
			int cur=i%2,tar=cur^1;
			ZERO(op[tar]);
			double p=s[i]*1.0/N;
			
			for(y=1;y<=N/2;y++) {
				double dp2[303]={};
				for(x=i+1;x>=0;x--) if(dp[x]) {
					if(s[i]==N) {
						dp2[x+1]+=dp[x];
						op[tar][y][x+1]+=dp[x]*(op[cur][y][x]+1);
					}
					else {
						dp2[x+1]+=dp[x]*p;
						dp2[x]+=dp[x]*(1-p);
						op[tar][y][x+1]+=dp[x]*    p*(op[cur][y][x]+(max(0,s[i]-y)+max(0,s[i]-(N-y)))*1.0/s[i]);
						op[tar][y][x]  +=dp[x]*(1-p)*(op[cur][y][x]+(1+min(y,N-s[i])-max(1,y-(s[i]-1)))*1.0/(N-s[i]));
					}
				}
				for(x=i+1;x>=0;x--) if(dp2[x]) op[tar][y][x] /= dp2[x];
			}
			for(x=i+1;x>=0;x--) {
				dp[x+1] += dp[x]*p;
				dp[x]   *= 1-p;
			}
		}
		
		double ret=0;
		FOR(i,L+1) {
			double ma=0;
			for(x=1;x<=N/2;x++) ma=max(ma,op[L%2][x][i]);
			ret+=dp[i]*(i+ma);
		}
		return ret;
	}
}

まとめ

なかなか複雑な状態遷移のDPだけど、「ある状態になる確率の期待値」と「得られるスコアの期待値」と異なる２値をDPしていくのが面白かった。