yukicoder contest 379

　Cまで三完。 Aに苦戦したのは反省。

コンテストへのリンク

No.2235 Line Up Colored Balls

　解説AC。

　期待値の線形性は考えたのだが、その後の考察がおかしかった。色が同じボールの間に他のボールが挟まる確率は……などと考えていたが、これでは線形性は使えない。

　（tester解の通りだが）ボールを順番に並べていくと考えて、

・（i番目と$i+1$番目が異なる確率）の総和と考える

　すると、

・色iのボールが最後以外で取り出される確率は$(S-1)/S$

・次のボールが色iでない確率は$(S-x_i)/(S-1)$

　から求めることができる。

No.2236 Lights Out On Simple Graph

　解説AC。

　半分全列挙と言われても頂点を半分にすることしか思い浮かばず、辺で半分全列挙すると思いつかなかった。