Hatena::Grouptopcoder

kuuso1の日記

2014-04-27

TCO round1C Hard

| 02:26 |  TCO round1C Hard - kuuso1の日記 を含むブックマーク はてなブックマーク -  TCO round1C Hard - kuuso1の日記

・無限にある1次元マス目に1台のロボットを置く。

・ロボットは1ステップにつき1マス等確率で右または左に移動する

・通ったマス目には色を塗る

・Nステップ後(N≦500)に塗られているマスの数の期待値を求める。

絵で描くとこんな感じ。□が塗られた箇所、●がロボットの位置。

f:id:kuuso1:20140428020651p:image

(絵を描ければ典型的な確率DPで計算できるが、本番中この絵が描けなかった。。。)

N回後に塗られている数(1~N)ごとに確率を計算する。

K個塗られていて、かつロボットが端にいるときだけ、確率0.5で塗られる個数=K+1になる。

どこにいるかはその前のターンにどこにいたかで決まるが、図を見ればわかるように

絶対座標にはあまり意味がなくて、いくつ塗られている中のどこにいるかだけで決まる。

なので、「塗られている個数×その中のロボットの相対位置」でDPできる。

public class RedPaint {
	public double expectedCells(int N) {
		if(N==0)return 1.0;
		double[,,] P=new double[2,N+2,N+1];
		for(int i=0;i<2;i++){
			for(int j=0;j<N+2;j++){
				for(int k=0;k<N+1;k++){
					P[i,j,k]=0.0;
				}
			}
		}
		P[0,1,0]=1.0;
		for(int i=1;i<=N;i++){//trial
			//init
			for(int j=0;j<=i+1;j++){
				for(int k=0;k<j;k++){
					P[1,j,k]=0.0;
				}
			}
			
			
			for(int j=1;j<=i;j++){//painted area
				for(int k=0;k<j;k++){//pos

					if(k==0){
						P[1,j+1,k]+=P[0,j,k]*0.5;
					}else{
						P[1,j,k-1]+=P[0,j,k]*0.5;
					}
					
					if(k==j-1){
						P[1,j+1,k+1]+=P[0,j,k]*0.5;
					}else{
						P[1,j,k+1]+=P[0,j,k]*0.5;
					}
				}
			}

			for(int j=0;j<=i+1;j++){
				for(int k=0;k<j;k++){
					P[0,j,k]=P[1,j,k];
				}
			}

		}											
		//calc Expectation;
		double Expect=0.0;
		for(int painted=1;painted<=N+1;painted++){
			double p=0;
			for(int pos=0;pos<painted;pos++){
				p+=P[1,painted,pos];
			}
			Expect+=p*painted;
		}
		return Expect;
		}
	}
}

ちなみに計算量はO(N^3)ですが、

dpテーブルをN+1×N+1×N+1で用意するとMLEする

dpテーブルを2×N+1×N+1 で用意して、新旧のテーブルを使いまわす、とすると

 テーブルのコピーをN+1×N+1で回すとTLEする

という2回の修正を経てSysTestPass。C#は定数倍も時々気をつけなければ。

あとちなみにTCOは最高順位775位(今回)で敗退。早解きゲーで残れない勝負弱さ。また来年。