AtCoder Beginner Contest #008, C : コイン

問題文

http://abc008.contest.atcoder.jp/tasks/abc008_3

問題概要

　表裏を区別できる N 枚のコインがあり、各コインには正整数が一つ書かれている。i 番のコインに書かれている整数は である。
　今、N 枚のコイン順列の内からランダムに選択された順序でコインを並べる。その後、以下の手順を適用する。

1. 全てのコインを表向きにする
2. 左のコインから順に、着目しているコインよりも右側にあるコインの内、着目しているコインの倍数が書かれたコインの表裏を反転する。

　手順終了後、表になっているコインの枚数の期待値を求めよ。

解法

　求める期待値は、E[ Σ( i 番目のコインでの期待値 ) ] なので、期待値の線形性より Σ( E[ i 番目のコインでの期待値 ] ) です。表になっているコインの枚数の総和は、あるコインが表になっているときに 1 増えるので、あるコインによる期待値はそのコインが表になっている確率と一致します。従って、i 番のコインが表になる確率を とおけば、先程の式は となり、各コインについてそれが表となる確率を求めることができれば、総和をとることで問題を解くことができます。
　さて、ある一つのコインに着目して、それが表になる確率を考えます。i 番のコインが表になる場合とは、それより左にあるコイン j であって、 が を割り切るものの枚数が偶数である場合です。このとき、関係のあるコインは（それ自身を含めて） を割り切る値が書かれたもののみです。そのようなコインの枚数を n とすると、それらのコインの内での i 番のコインの位置 ( 0-indexed ) は 0 から n - 1 のいずれかで、いずれも等確率 q = 1 / n で選択されます。更に、これらの位置の内で、左にあるコインの枚数が偶数となるものの数を n で表すと n を 2 で切り上げ整数除算した値になります。着目しているコインの位置は背反事象なので和事象の確率は単純な確率の和となり、従って、着目したあるコインによって得られる期待値は q * ( ( n + 1 ) / 2 ) となります。
　あとは、全てのコインについて上記のように期待値を計算して足し合わせれば全体の答えが求まります。

コード

using VI = vector<int>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	double res = 0;
	REP( i, 0, n )
	{
		const int c = count_if( ALL( as ), [&]( int a ){ return !( as[i] % a ); } );
		const double p = 1. / c;
		res += p * ( ( c + 1 ) / 2 );
	}

	cout << setprecision( 8 ) << fixed << res << endl;

	return 0;
}