yukicoder contest 380 G
解き方
この問題では$ H \le W としても一般性を失わないため、この記事においては$ H \le W とする。
（もし$ H \gt W であったばあいは$ H と$ W を入れ換えれば良い）
また、この記事においては簡単のために、$ HW 個のマスに書き込まれる数が全て異なる場合のみ考える。
ほとんど確実に（almost surely）$ HW 個のマスに書き込まれる数が全て異なるため、このような場合のみ考えても問題ない。 言い換えれば、ある$ 2 つの異なるマスに同じ数が書き込まれているような場合の確率は$ 0 であるため無視をする。
いきなりスコアの期待値を求めるのは難しいため、以下の2つについてそれぞれ考える。
1. $ HW 個の数のうち、何番目に小さい数の$ K 乗がスコアになるか（$ l 番目に小さい数の$ K 乗がスコアとなる確率を$ p_{l} とする）
2. $ HW 個の数のうち$ l 番目に小さい数の期待値はいくつになるか（この期待値を$ e_{l} とする）
$ l 番目に小さい数の$ K 乗がスコアになるという事象と、$ l 番目に小さい数の値に関する事象は明らかに独立である。
よって、もとめる期待値は$ \sum_{l} p_{l} \times e_{l} となるため、各$ l について$ p_{l} と$ e_{l} をそれぞれ求めれば良い。
まずは、$ p_{l} について考える。
マスに書かれた数が小さい順に、各マスに$ 1 から$ HW の番号をつけることを考える。
冒頭に述べた通り、マスに書かれた全ての数が異なる場合のみ考えているため、各マスの番号は一意に決まる。
マスの番号の付け方は$ (HW)! 通りあるが、対称性を考慮すると、これらは全て等確率に現れる。
$ HW 個の数のうち、何番目に小さい数の$ K 乗がスコアになるかは、このマスの番号の付け方のみに依存する。
よって、各$ l について、$ l 番目に小さい数の$ K 乗がスコアになる場合の番号の付け方が何通りあるか考えれば良い。
スコアは通ったマスに書かれた数のうち小さい方から2番目の数を使って定められるため、$ p_{l} に意味があるのは$ l \ge 2 のときである。
このとき、$ p_{l} は下記の2条件を同時に満たす確率である。
$ l 未満の番号が書かれた$ l-1 個のマスのうち$ 2 つ以上のマスを通るような経路が存在しない
$ l の番号が書かれたマスを通り、かつ$ l 未満の番号が書かれたマスを通る経路が存在する
1つ目の条件を満たすためには、$ l-1 個のマスを行番号の昇順に並べたとき、列番号が降順となっている必要がある。
逆に、そのような条件を満たせば1つ目の条件が満たされることもわかるため、行と列をそれぞれ独立に$ l-1 個決めれば良い。
よって、$ l-1 個のマスの配置は$ {}_{H} C_{l-1} \times {}_{W} C_{l-1} \times (l-1)! 通り存在する。
次に2つ目の条件を満たすような$ l の番号が書かれたマスの決め方だが、残りのマスから選ぶことを考えると$ HW-l+1 通りある。
ただし、$ l 以下の番号が書かれた$ l 個のマスのうち$ 2 つ以上のマスを通るような経路が存在しない場合を除く必要がある。
残りのマスについては2つの条件に影響はないため、番号の付け方は$ (HW-l)! 通り考えられる。結局$ p_{l} は下のようになる。
$ p_{l} = \frac{(HW-l)!}{(HW)!} \times ((HW-l+1) \times {}_{H} C_{l-1} \times {}_{W} C_{l-1} \times (l-1)! - {}_{H} C_{l} \times {}_{W} C_{l} \times l!)
実際に計算することを考えて書き換えると以下のようになる。
$ p_{l} = \frac{(HW-l+1) \times {}_{H} C_{l-1} \times {}_{W} C_{l-1} \times (l-1)! - {}_{H} C_{l} \times {}_{W} C_{l} \times l!}{{}_{HW} P_{l} }
この式からもわかる通り、$ p_{l} に意味があるのは$ l-1 \le H のときである。よって、$ 2 \le l \le H+1 のときのみ考えれば良い。
以上より$ p_{l} が求められたため、次は$ e_{l} を求める。
$ e_{l} は、同一の分布に従う独立な確率変数$ HW 個のうち、小さい方から$ l 番目の値の期待値である。
このような期待値の求め方については、例えばこの記事においても述べられているため、それに従って求める。 まず、$ 0 以上$ 1 以下の実数値を取るような一様分布に従う確率変数$ X をとり、$ Y = X^{K} とする。
また、$ Y と同一の分布に従う独立な確率変数を$ HW 個考えたとき、小さい方から$ l 番目の値を表す確率変数を$ Z とする。
$ Y の累積分布関数を$ F_{Y} とし、確率密度関数を$ f_{Y} とする。また、$ Z の確率密度関数を$ f_{Z} とする。
このとき、$ e_{l} は$ Z の期待値であるため、$ e_{l} = \int_{0}^{1} x f_{Z} (x) dx である。
先に紹介した記事によれば、$ f_{Z}(x) = l \times {}_{HW} C_{l} \times F_{Y} (x) ^{l-1} \times (1-F_{Y}(x))^{HW-l} \times f_{Y}(x) である。
定義より$ f_{Y} (x) = \frac{d}{dx} F_{Y} (x) であるため、$ t = F(X) と置くことで上の積分は下のようになる。
$ e_{l} = \int_{0}^{1} l \times {}_{HW} C_{l} \times F_{Y}^{-1} (t) \times t^{l-1}(1-t)^{HW-l} dt
$ F_{Y}^{-1} (t) = t^{K} より、$ e_{l} = l \times {}_{HW} C_{l} \times \int_{0}^{1} t^{l+K-1}(1-t)^{HW-l} dt = l \times {}_{HW} C_{l} \times B(l+K, HW-l+1) となる。
ただし、上の式において$ B はベータ関数である。正整数に対するベータ関数は階乗を使って表せるため、整理すると下のようになる。 $ e_{l} = l \times \frac{(HW)!(l+K-1)!}{l!(HW+K)!} =\frac{l \times {}_{l+K-1} P_{K-1}}{{}_{HW+K} P_{K}}
以上より、$ 2 \le l \le H+1 において$ p_{l} と$ e_{l} を求めることができたため、$ \sum_{l=2}^{H+1} p_{l} \times e_{l} を計算すればスコアの期待値が求められる。
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
long long power_mod (long long a, long long b, long long mod_num) {
long long ans = 1LL;
if (b > 0LL) {
ans = power_mod(a, b/2LL, mod_num);
ans = (ans * ans) % mod_num;
if (b%2LL == 1LL) {
ans = (ans * (a % mod_num)) % mod_num;
}
}
return ans;
}
int main () {
int h = 0;
int w = 0;
int k = 0;
int res = 0;
long long ans = 0LL;
long long mod_num = 998244353;
long long hw = 0LL;
long long div = 1LL;
long long fact60001 = {}; long long invf60001 = {}; res = scanf("%d", &h);
res = scanf("%d", &w);
res = scanf("%d", &k);
if (h > w) {
int swap = h;
h = w;
w = swap;
}
hw = ((long long)h)*((long long)w);
for (int i = 0; i < k; i++) {
div *= hw+((long long)(k-i));
div %= mod_num;
}
for (int i = 0; i < w+k; i++) {
facti+1 *= (long long) (i+1); }
invfw+k = power_mod(factw+k, mod_num-2LL, mod_num); for (int i = w+k; i > 0; i--) {
}
div = (div*hw)%mod_num;
for (int i = 1; i <= h; i++) {
long long tmp = hw-((long long)i);
tmp %= mod_num;
tmp %= mod_num;
tmp %= mod_num;
tmp %= mod_num;
tmp %= mod_num;
tmp %= mod_num;
tmp %= mod_num;
if (i < h) {
sub %= mod_num;
sub %= mod_num;
sub %= mod_num;
sub %= mod_num;
sub %= mod_num;
tmp += mod_num-sub%mod_num;
tmp %= mod_num;
}
tmp %= mod_num;
tmp %= mod_num;
div *= hw-((long long)i);
div %= mod_num;
ans += (tmp*power_mod(div, mod_num-2LL, mod_num))%mod_num;
}
printf("%lld\n", ans%mod_num);
return 0;
}
私の提出一覧
table: submissions_yukicoder_contest_380_G
提出のURL 提出時刻 結果 備考
感想
コンテストではD問題で時間をとられて30分間強しか残っていなかったので、半ば諦めながらE問題をみた。
E問題を少し考えて解けなかったため、F問題をちらっと見た気もするが、G問題が確率の問題だったためG問題を考えることに。
上の解き方に書いた$ p_{l} についてはコンテスト中にある程度イメージがついていたけれど、$ e_{l} が難しいなと考えていた。
解き方のなかで紹介した記事をみつけて、$ K=1 であれば記事に書かれた式と$ p_{l} を合わせて解けそうだと思った。
一般の$ K に関しては少し面倒だけれど、記事に書かれた積分を計算すれば求められるかなと思ったあたりまでがコンテスト中。
コンテスト後に改めて上で紹介した記事をよくみたら、ベータ関数に帰着されるから自分で積分計算する必要はないことに気づいた。
そこでWikipedia からベータ関数の値の式を探して、ようやく$ e_{l} も求めることができたので、あとは実装するだけ。
思い返せば、積分を変数変換してベータ関数に帰着すれば良いこと以外はコンテスト中に思いつけていて、とっつきやすい問題やったかな。
twitter でこのあたりのこともつぶやいているけれどその中でなぜかベータ関数をベルヌーイ関数と書いてしまっていて恥ずかしい。