問題リンク

解法

( 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 ) binom ( w, k )

となりますね。さらに ( j + 1) binom ( h, j ), ( w + 1 ) binom ( w, k ) は展開して j binom ( h, j ) などにして、それぞれまとめられますね。そうして出てきた式は二項係数の畳み込みになっており、それもまとめて、その後先頭の二項係数の逆数と約分すると、

E [ Xᵢ ] = ( h w i ( i - 1 ) ) / ( h + w ) ( h + w - 1 ) + i + 1

となります。これの総和を取って、

E [ X ] = ( h w k ( k - 1 ) ( k + 1 ) ) / ( 3 ( h + w ) ( h + w - 1 ) + k ( k + 3 ) / 2

がわかります。これの ( h + w ) ! / ( w + w - k ) ! 倍が答えです。