ngtkana https://blog.hatena.ne.jp/ngtkana/ ブログ名 https://blog.ngtkana.com/ 問題リンク atcoder.jp 解法 ( h + w ) ! / ( w + w - k ) ! 通りのカットが等確率で起こるとして、スコア X の期待値 E [ X ] を計算しましょう。これは実は Θ ( lg p ) （除算が律速）で解けます。 各 1 ≤ i ≤ k に対して、第 i 回のカットによるスコアを X _ i と置きましょう。すると X = X₁ + ... + Xₖ が成り立ちます。さて各 Xᵢ の期待値を計算します。 E [ Xᵢ ] = binom ( h + w, i ) ⁻¹ ∑ⱼ₊ₖ₌ᵢ ( j + 1 ) ( w + 1 ) binom ( h, j ) b… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2021%2F05%2F08%2F155217" title="キーエンス プログラミング コンテスト 2019 F - Paper Cutting の公式解説とは異なる、クローズドフォーミュラによる解法 - ブログ名" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-05-08 15:52:17 rich https://blog.ngtkana.com/entry/2021/05/08/155217 1.0 100%