yukicoder contest 379 D
解き方
※ ここに書く解き方は、解説に書かれているものと考え方や最終的な式はほとんど同じであるが、導出過程の説明が少し異なる この解説において、数列$ x_{1}, x_{2}, \ldots, x_{N} の総和を$ S_{1} とし、各項を2乗した値の総和を$ S_{2} とする。
すなわち、$ S_{1} = \sum_{i = 1}^{N} x_{i} かつ$ S_{2} = \sum_{i = 1}^{N} x_{i}^{2} である。
ここで、ボールを一列に並べたとき、隣り合うボールが異なる色である位置の個数に$ 1 を足すと、このボールの列の不連続度となる。
よって、隣り合うボールが異なる色である位置の個数の期待値を$ E とすると、求めるべき不連続度の期待値は$ E+1 となる。
このことから、不連続度の期待値を求めるには$ E の値が求まれば十分であるため、以降は$ E の値を求めることを考える。
ここで、簡単のために同じ色のボール同士であっても区別できるとみなす（例えば各ボールにユニークな番号が書かれている場合とか）。
同じ色のボール同士が区別できたとしても、不連続度は変化せず、求める期待値も変わらないため、このようにみなしても問題ない。
このとき、全てのボールを一列に並べる場合の数は$ S_{1} ! 通りあるが、対称性からこれらは全て等確率に現れる。
また、任意の異なる2つのボールの組$ a と$ b について、この2つがこの順に隣り合うようなボールの並べ方は$ (S_{1}-1)! 通りある。
よって、この問題に書かれた操作でボールを一列に並べたとき、$ a と$ b がこの順に隣り合う確率は$ \frac{(S_{1}-1)!}{S_{1} !} = \frac{1}{S_{1}} となる。
期待値の線形性により、$ S_{1} 個のボールの中で、色が異なっている2つのボールの順序 組の個数に$ \frac{1}{S_{1}} をかけると$ E となる。
色$ i のボールと色$ j のボールの2つ組の個数は$ x_{i} x_{j} であるため、$ E = \frac{\sum_{i \neq j } x_{i}x_{j}}{S_{1}} = \frac{S_{1}^{2}-S_{2}}{S_{1}} となる。
以上より、$ E が求められたため、この値を用いて不連続度の期待値も求めることができる。
解答例
下は上記の方法で解いたときの提出結果である。また、上記の提出の際に提出したソースコードをその下に転記する。
code: C
long long power_mod (long long a, long long b, long long mod_num) {
long long ans = 1LL;
if (b > 0LL) {
ans = power_mod(a, b/2LL, mod_num);
ans = (ans * ans) % mod_num;
if (b%2LL == 1LL) {
ans = (ans * (a % mod_num)) % mod_num;
}
}
return ans;
}
int main () {
int n = 0;
long long x = 0LL;
int res = 0;
long long ans = 0LL;
long long mod_num = 1000000007LL;
long long sum_sq = 0LL;
res = scanf("%d", &n);
for (int i = 0; i < n; i++) {
res = scanf("%lld", &x);
ans += x;
sum_sq += x*x;
}
ans = ((ans*ans-sum_sq)%mod_num)*power_mod(ans, mod_num-2LL, mod_num)+1LL;
printf("%lld\n", ans%mod_num);
return 0;
}
私の提出一覧
table: submissions_yukicoder_contest_379_D
提出のURL 提出時刻 結果 備考
感想
今でこそ、確率の問題を考えるときの個人的な常套手段が板についた気もする。高校生だった頃は、ここまでできなかったと思う。
（区別されないものを敢えて区別したり、対称性から等確率であることを理解したり、細かい事象に分けて期待値の線形性を利用したり）
最終的に、「総和の2乗」と「2乗の総和」の差になるのは面白いと感じた。分散を思い出すかな。