ABC194参加しました。

A - I Scream

似たような用語がたくさんあってややこしいですね... ただ、問題自体はifを列挙すればいいだけです。

B - Job Assignment

タスクAに挑む人を一人仮で決めた状態でタスクBに挑む人を選んで、かかる時間を計算していく総当り法

C - Squared Error

素直に解いたら, forの二重ループになります。これは$\mathcal{O}{(N^{2})} $ オーダーで間に合いません。この手の数式の値を求めろ、のようなシンプルな問題は、まず式変形を考えてます(それ以外にヒントもないので...)。 N=4の場合は

$$ \begin{align} \sum_{i=2}^{4} \sum_{j=1}^{i-1} { (A_{i}-A_{j})^{2}}　&= (A_{2} - A_{1})^{2}\\ &+ (A_{3} - A_{1})^{2} + (A_{3} - A_{2})^{2} \\ &+ (A_{4} - A_{1})^{2} + (A_{4} - A_{2})^{2} + (A_{4} - A_{3})^{2}\\ &= A_{2}^{2} -2A_{2}A_{1} + A_{1}^{2}\\ &+ A_{3}^{2} -2A_{3}A_{1} + A_{1}^{2} + A_{3}^{2} -2A_{3}A_{2} + A_{2}^{2}\\ &+ A_{4}^{2} -2A_{4}A_{1} + A_{1}^{2} + A_{4}^{2} -2A_{4}A_{2} + A_{2}^{2} + A_{4}^{2} -2A_{4}A_{3} + A_{3}^{2}\\ &= 3(A_{1}^{2} + A_{2}^{2} + A_{3}^{2} + A_{4}^{2}) - 2(A_{1}(A_{2} + A_{3} + A_{4}) + A_{2}(A_{3} + A_{4}) + A_{3}A_{4}) \end{align} $$

となります。式の最後に着目すると、第一項目は$\mathcal{O}(N) $ です。第二項目は

long diff = 0;
long sum = Aの総和
for(int i = 0; i < Aのサイズ-1; ++i)
{
    t -= A[i];
    diff += A[i] * t;
}

みたいに計算します。最初に累積和を取ると、計算が早いです。一般化すれば $$ (N-1)(A_{1}^{2} + A_{2}^{2} + ...) - 2(A_{1}(A_{2} + ... + A_{N}) + A_{2}(A_{3} + ... + A_{N}) + ... + A_{N-1}A_{N}) $$ となるでしょうか。

公式解説のように、出てくる値の制約条件を使って解く方法もあるようです。解説 - AtCoder Beginner Contest 194

D - Journey

コンプガチャ問題。マス目をガチャの景品と置き換えると、景品を全部手に入れるまでの期待値を計算することになります。(最初から景品は一つ入手済み、かつ、全景品は等確率で排出される)

コンプガチャに必要な回数の期待値の計算 | 高校数学の美しい物語にありますが、ここと違うのは、最初から一つ景品を入手済みであること。

公式解説にもある通り「確率 $p(p≠0)$ で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は $1/p$ である。」を利用します。なんでこうなるかは後ほど説明。

このとき、結局全部の景品を取るまでの期待値なので、景品数4つの場合は

1回目は$3/4$ の確率で新しいのがでる。逆に、$ 1/4 $の確率で外れ(いままで入手したのと同じもの)
2回目は$2/4$ の確率で新しいのがでる。逆に、$ 2/4 $の確率で外れ(いままで入手したのと同じもの)
最終回は$1/4$ の確率で新しいのがでる。逆に、$ 3/4 $の確率で外れ(いままで入手したのと同じもの)

となります。つまり一般化すると、

1回目は$(N-1)/N$ の確率で新しいのがでる。逆に、$ 1/N $の確率で外れ(いままで入手したのと同じもの)
2回目は$(N-2)/N$ の確率で新しいのがでる。逆に、$ 2/N $の確率で外れ(いままで入手したのと同じもの)
(繰り返し)
最終回は$1/N$ の確率で新しいのがでる。逆に、$ (N-1)/N $の確率で外れ(いままで入手したのと同じもの)

です。i回目の期待値は最初に書いたとおり、成功する確率の逆数になるので、$(N-i)/N$です。これをforで足し合わせていきます。

double ans = 0.0;
for(int i = N-1; i >= 1; --i)
{
   ans += 1.0 / ((double)i / (double)N);
}

Journey [AtCoder Beginner Contest 194 D] - はまやんはまやんはまやん

冒頭の定理(あたり確率の逆数が期待値になる)ですが、「幾何分布の期待値」になります。

公式解説動画でも解説してますが、Python で解く AtCoder M-SOLUTION プロコンオープン C - owlogとか、幾何分布とは？期待値（平均）や分散の証明はどうなってる？｜いちばんやさしい、医療統計でも解説してます。

備忘録がてら書いておきます。期待値を$E$とすると、以下が成立します(成立過程はここから)

$$
\begin{align} E &= \sum_{n=1}^{\infty}{np(1-p)^{n-1}}\\ &= p \sum_{n=1}^{\infty}{n(1-p)^{n-1}}\\ &= p (1 + 2(1-p) + 3(1-p)^{2} + ... ) \end{align} $$

ここで$E$に$1-p$を掛けて

$$ (1-p)E = p ((1-p) + 2(1-p)^{2} + ... ) $$

なので、

$$ \begin{align} E-(1-p)E &= p (1+(1-p) + (1-p)^{2} + ... )\\ pE &= p \sum_{n=1}^{\infty} {(1-p)^{n-1}} \\ E &=\sum_{n=1}^{\infty} {(1-p)^{n-1}} \end{align} $$

あとは無限等比級数の公式から

$$ \begin{align} E &= \frac{1}{1-(1-p)} \\ E &= \frac{1}{p} \end{align} $$

となります。

まとめ

今回は結果さえ知っていれば解けましたが、やっぱり確率は苦手。

umem0chiの日記

AtCoder ABC194

A - I Scream

B - Job Assignment

C - Squared Error

D - Journey

まとめ