第６回ドワコン B - Fusing Slimes

問題原文

問題要旨

$N$ 匹のスライムが一直線上に並んでいる。左から $i$ 番目のスライムは、座標 $x_i$ にいる。
ニワンゴ君は以下の操作を $N - 1$ 回繰り返す。

$N$ 番目（一番右）じゃないスライムの中からランダムに１匹選ぶ。
選ばれたスライムは、他のスライムにぶつかるまで右に移動する。ぶつかったあとは、１匹のスライムとして扱う。

$N - 1$ 回の操作によって、スライムが移動した距離の総和の期待値に $(N - 1)!$ をかけた値を、 $10^{9} + 7$ で割ったあまりを求めよ。

解法

結局求めたいものはなに？

求められる出力がなんかややこしい。
まず、求めたい期待値は、 $\frac{全パターンについて、スライムが移動した距離の総和}{全パターンの通り数}$ である。
次に、(全パターンの通り数) 、これは明らかに $(N - 1)!$ 通りである。
出力する際には、 $(N - 1)!$ をかけるので、結局出力するのは、『全パターンについて、スライムが移動した距離の総和』となる。

各スライムがどのぐらい動くか → 各区間が何回カウントされるか

頑張って発想を転換しよう！w

f:id:AT274:20200113220458p:plain — 各スライムがどれぐらい動くか？

これから！

f:id:AT274:20200113221047p:plain — 各区間が何回カウントされるか

こうだ！！！w

各区間がカウントされる確率は？

f:id:AT274:20200113221619p:plain — ある区間がカウントされるには・・・？

こんな感じ。最後に選ばれないと、途中で他のスライムにぶつかってくっついてしまう。
結局、ある区間がカウントされる確率は、１つ離れてるなら $\frac{1}{1}$ 、２つなら $\frac{1}{2}$ 、３つなら $\frac{1}{3}$ となる！
あとはこの計算を、全てのスライム × そのスライムの右側にある区間分全部計算すればいい！！！

実装

逆元を使う & 累積和っぽい実装をすれば $O(N)$ でできるんですねぇ！感動！

N = int(input())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7

# 間の距離を計算
distances = [0] + [X[i + 1] - X[i] for i in range(N - 1)]

# (N - 1)!を計算
factorial_n_1 = 1
for i in range(1, N):
    factorial_n_1 *= i
    factorial_n_1 %= MOD


expected_cnt = [0] * N
for i in range(1, N):
    expected_cnt[i] = expected_cnt[i - 1] + (factorial_n_1 * pow(i, MOD - 2, MOD)) % MOD

moves = [(d * e) % MOD for d, e in zip(distances, expected_cnt)]
print(sum(moves) % MOD)

感想

むずいけど、閃き一発でなんとかなりそうな気がしますね。。。！
「何回数えられるか？に見方を変える」、すごいいい勉強になりました！

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。