AtCoder AGC #020 : F - Arcs on a Circle

これは問題も解法もシンプル。
https://agc020.contest.atcoder.jp/tasks/agc020_f

問題

円周の長さLの円がある。
ここにN個の円弧を重ねる。個々の円弧の長さはC[i]である。

複数の円弧が同じ領域に重なってもよい。
各円弧の配置位置が当確率でランダムに定まるとき、円全体が最低1個の円弧で覆われている確率を求めよ。

解法

なお、円のままだと扱いづらいので、一番長い円弧aを1つ選び、それの左端を座標0とし、そこから右に長さLの直線があると考える。
[0,C[a]]はすでに覆われていて、(C[a]L)はまだ覆われていない。

L,Cが整数なことから、円弧の開始位置を整数部分と小数部分に分けて考えよう。
この時、小数部分の細かい値はどうでもよく円弧間での大小関係のみ関係する。
例えば、a,bを[0,1)の範囲の実数とするとき、ある円弧の右端の座標が5+aで、別の円弧の左端の座標が5+bの場合に両者の間に隙間ができるかどうかはa≧bかどうかできまる。

よって、一番長い円弧以外の円弧について、小数部分の大小関係を(N-1)!通り総当たりしよう。
これらは互いに1/(N-1)!の確率で生じる。
このそれぞれにおいて、円全体が覆われる確率を考えよう。
ここまで来るとDPで以下の状態を考える。
f(x,R,bitmask) := 今座標xを考える時、[0,R]がすでに覆われていて、bitmaskに示す円弧が配置済み、という状態になる確率
小数部分の大小関係で各円弧の開始位置は分けているため、座標xにおいて新規における円弧は一意に定まる。
あとはその円弧を置く場合と置かない場合それぞれ考えていけばよい。

int N,C;
int L[10];
int D[10];

double dp[303][32];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	FOR(i,N) cin>>L[i], D[i]=i;
	sort(L,L+N);
	
	double ret=0;
	do {
		ZERO(dp);
		dp[N*L[N-1]][0]=1;
		FOR(i,N*C) if(i%N) {
			x=D[(i-1)%N];
			for(int mask=0;mask<1<<(N-1);mask++) if((mask&(1<<x))==0) {
				for(y=i;y<=N*C;y++) {
					dp[min(N*C,max(y,i+L[x]*N))][mask ^ (1<<x)] += dp[y][mask];
				}
			}
		}
		
		ret += dp[N*C][(1<<(N-1))-1] ;
	} while(next_permutation(D,D+(N-1)));
	
	FOR(i,N-1) ret/=i+1;
	_P("%.12lf\n",ret/pow(C,N-1));
}

まとめ

2100ptとは思えないコードの短さ。