TopCoder SRM 852 : Div1 Easy Div2 Hard RandomizedParking

せっかくSRM852でHighest更新したのに、PracticeRoomが開かないままSRM853が始まってレートを落としてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=18153

問題

円周状にN個のスロットがある駐車場がある。
駐車するために来た車は任意のスロットの前から駐車場に進入し、空きスロットを見つけるまで時計回りに移動する。
スロットの初期状態が与えられる。
この後、車がランダムな位置から駐車場に進入する場合、K台目に来る車は空きスロットを見つけるまでどのぐらい移動する必要があるか、期待値を求めよ。

解法

スロット数は少ないので、BitDPの要領でスロットの空きパターンに対応する、その状態に至る確率を計算していけばよい。

double pat[1<<20];
class RandomizedParking {
	public:
	double solve(string start, int K) {
		int mat=0;
		int N=start.size();
		int i,x,y;
		FOR(i,N) if(start[i]=='X') mat|=1<<i;
		double sum=0;
		int mask;
		FOR(mask,1<<N) pat[mask]=0;
		pat[mat]=1;
		FOR(mask,1<<N) if(pat[mask]) {
			
			FOR(x,N) {
				FOR(y,N) {
					if((mask&(1<<((x+y)%N)))==0) {
						if(__builtin_popcount(mask)==__builtin_popcount(mat)+K-1) {
							sum+=y*pat[mask]/N;
						}
						else {
							pat[mask|(1<<((x+y)%N))]+=pat[mask]/N;
						}
						break;
					}
				}
			}
			
		}
		
		return sum;
		
	}
}

まとめ

こちらは簡単。