今週の胎界主を読んだ。九狼が意外と物申す体制になっている。これはアバドンではなく本人の意思でいいんだよな？今まで曲がりなりにも父を慕ってる感じだったので、どういう感情でこの発言をしているのかが掴めない。一度ちゃんとぶつかっておきたかったのだろうか。

一方レックス、前話最後ですごい剣幕になっていたが、今回はいつも通りの感じになっている。アバドンに気付いた上で「スムーズに事が運ぶようかましてる」のだろうか。無責任飛行の時と比べて子育て論語りが雑になってないか。アドニスみたくかかと浮いてるし。

久松はこれ大丈夫なのか？正の字カウントで5つ不躾な物言いしたら爆発するとかだったら嫌だぞ。

ところで読み直したら「月曜日 2」p26のイメージでレックス靴脱いどる。これは一体？

本筋とは関係ないが、久松ののれんが「久」の字になってるのに気づいてニヤニヤしている。

---

今日解いた競プロの問題。

ABC295-E: 解説AC。

期待値の定義から考えると$\sum_{i=1}^M P(A_K=i)\times i$だが、$P(A_K=i)$を直接求めるのは難しい。一方$P(A_K\leq i)$は割と求めやすい。これを求めた上でなら$P(A_K=i)=P(A_K\leq i)-P(A_K<i)$という形で求めることができる。

$P(A_K\leq i)$の条件を考えると、これは$i$以下の値を持つ要素が$K$個以上あることと同値になる。元の配列A(から0を取り除いたもの)に$i$以下の値が$K$個以上あれば確率は1になる。一方で$i$以下の値と0の数を全て合わせても$K$個に届かなければ確率は0。問題はその間で、これは多少地道に計算する必要がある。0の数を$z$として、$K$個に届くために追加で必要な$i$以下の値の最低限の数を$z_0$とすると以下のようになる。

$\sum_{j=z_0}^z i^j (M-i)^{z-j} \ _zC_j$

$z$個中$j$個が$i$以下で$z-j$個が$i$より大きいというのを愚直に式にすればこうなる。これは特に特殊な工夫をして高速化しなくとも、前計算で二項係数を$O(1)$でやるいつものやつと二分累乗をすれば$O(N\log N)$で求まる。これを$1\leq i \leq M$について計算すれば$O(MN\log N)$で解けた。

なお、べき乗を前計算しておけば計算量を落とせる。前計算する範囲は$i^j(0\leq i \leq M, 0\leq j \leq N)$なので前計算含めて$O(MN)$になる。