TopCoder SRM 603 Div2 Hard GraphWalkWithProbabilities

解けはしたけどあまりすっきりしない解き方。
http://community.topcoder.com/stat?c=problem_statement&pm=12908

問題

有向グラフと、グラフ上の初期位置が与えられる。
プレイヤーは１ターンごとにその場にとどまるか、辺に沿った隣接点に移動する。

その際、各点には勝率win[i]とloose[i]が与えられており、それぞれの確率で勝利または敗北する。
winとlooseの和は1とは限らず、winでもlooseでもない場合は次のターンに進む。
プレイヤーが最適手を取った場合の勝率の期待値を求めよ。

解法

winが大きい点がある場合、そこに移動して後は勝つか負けるかするまでずっとその点にいればよい。
よって、後はいかにそのような最適点に移動するかが決め手となる。

各頂点において、(その点に到達するまでの勝率,その点に到達するまでの負け確率,その点に到達してまだ決着がつかない確率)を管理していく。
実際は３つの合計は1なので、このうち２つ、勝率・負け確率のペアを管理し、フロイト法の容量で頂点間を遷移していけばよい。

なお、処理を繰り返すと勝率・負け確率のペアが無限に膨らんで発散するので、処理途中で確定した最大勝率がある場合、その負け確率が(1-最大勝率)となるような遷移は避けることでいずれ収束する。
また、明らかに不利な遷移、たとえばより勝率が高く負け確率が低いような状態がすでにある場合を避けることでも状態数を削減できる。

class GraphWalkWithProbabilities {
	public:
	double findprob(vector <string> graph, vector <int> winprob, vector <int> looseprob, int Start) {
		int N=graph.size();
		int i,x,y;
		FOR(x,N) graph[x][x]='0';
		
		double ma=0;
		map<double,double> M[51];
		map<double,double> DM[51];
		M[Start][0]=DM[Start][0]=0;
		FOR(i,100) {
			map<double,double> DM2[51];
			FOR(x,N) FOR(y,N) if(graph[x][y]=='1') {
				ITR(it,DM[x]) {
					double wi = it->first;
					double lo = it->second;
					if(abs(1-(wi+lo))<1e-9) continue;
					if(1-lo<ma) continue;
					
					double al = 1.0-wi-lo;
					DM2[y][wi+al*winprob[y]/100.0] = lo+al*looseprob[y]/100.0;
				}
			}
			FOR(x,N) {
				DM[x].clear();
				ITR(it,DM2[x]) {
					double wi = it->first;
					double lo = it->second;
					
					ma=max(ma,wi+(1-wi-lo)*winprob[x]/(winprob[x]+looseprob[x]));
					if(1-lo<ma) continue;
					
					if(M[x].find(wi)!=M[x].end() && M[x][wi]<=lo) continue;
					pair<map<double,double>::iterator,bool> p=M[x].insert(*it);
					map<double,double>::iterator p2=p.first;
					p2++;
					if(p2!=M[x].end() && p2->second<=p.first->second) {
						M[x].erase(p.first);
						continue;
					}
					DM[x][wi]=lo;
				}
			}
		}
		
		FOR(x,N) ITR(it,M[x]) {
			double lef=(1-it->first-it->second)*winprob[x]/(winprob[x]+looseprob[x]);
			ma=max(ma,it->first+lef);
		}
		return ma;
	}
};

まとめ

もっと丁寧に状態管理しないと状態数が発散すると思ったけど、あっさり通ってしまって拍子抜け。
Editorialが出たらより良い解法を見てみる。