Codeforces Round #612 (Div. 1) D. LCC

Problem - D - Codeforces

異常実装になったけどなんとか自力で解けた…

問題概要

数直線上に $n$ 個の粒子がある。粒子 $i$ は初期位置 $x_{i}$ 、速さ $v_{i}$ 、右に動く確率 $p_{i}$ で特徴づけられる。

この粒子を用いて以下の実験を行う。

まず各粒子の移動方向を確率に従って決める。粒子 $i$ が右に動く確率は $p_{i}$ 、左に動く確率は $1-p_{i}$ である。
全ての粒子が時刻 $0$ にそれぞれの初期位置 $x_{i}$ からスタートし、先ほど決めた向きにそれぞれの速さ $v_{i}$ で動く。
いずれか2つの粒子が衝突した時点で実験を終了し、その時刻を実験の経過時間とする。ただし永遠に粒子が衝突しない場合は経過時間 $0$ とする。

実験の経過時間の期待値を求めよ。この値は有理数になるので $\bmod 998244353$ の形式で出力せよ。

制約

$1 \le n \le 10^{5}$
$-10^{9} \le x_{1} \lt \cdots \lt x_{n} \le 10^{9}$
$1 \le v_{i} \le 10^{6}$
$p_{i}$ は百分率で与えられ、 $0 \le p_{i} \le 100$

解法

記法

連続するいくつかの粒子の移動方向を、L と R を並べたものとして記します。例えば2つの粒子が向かい合って移動していることを RL のように表記します。

以降の説明では $p_{i}$ は百分率の値ではなく確率そのものとして扱います。

衝突として考えるべきもの

いずれかの粒子が衝突した時点で終わりなので、考えるべき衝突は隣り合う2つの粒子のものだけです。粒子 $i$ と粒子 $i+1$ の衝突として以下のような場合があり得ます。

2粒子の移動方向が向かい合っている（RL）場合：時刻 $\frac{x_{i+1}-x_{i}}{v_{i+1}+v_{i}}$ で衝突する。
2粒子の移動方向がともに左（LL）であり、 $v_{i} \lt v_{i+1}$ である場合：時刻 $\frac{x_{i+1}-x_{i}}{v_{i+1}-v_{i}}$ で衝突する。
2粒子の移動方向がともに右（RR）であり、 $v_{i} \gt v_{i+1}$ である場合：時刻 $\frac{x_{i+1}-x_{i}}{v_{i}-v_{i+1}}$ で衝突する。

ここで、向かい合っている場合に衝突する時刻のほうが、同じ方向に動く場合に衝突する時刻より必ず早いことに注意しておきます。

全ての2粒子間においてこれらの衝突候補時刻を計算し、時刻順にソートしておきます。時刻は有理数として持っておいて、ソートのための比較関数では通分すると誤差がなくて良いです。

期待値を計算するアウトライン

まず期待値計算の概略を説明します。

時刻 $t$ で実験が継続している確率を $P(t)$ とします。 $P(0) = 1$ であり、この値は先ほど計算した衝突候補時刻でのみ減少します。

$P(t)$ を以下の図の赤線として図示すると、求めたい期待値は青く塗りつぶした領域の面積として計算できます。

f:id:betrue12:20200106233513p:plain

衝突候補時刻 $t$ において $P(t)$ が減少した量を $\Delta(t)$ と書くことにすると、この面積は $t\times\Delta(t)$ を全ての衝突候補時刻について合計したものとして計算することができます。図の青領域を横に短冊状に切るイメージです。

これでこの問題は、各衝突候補時刻を順番に見ていきながら「各粒子の移動方向が、それまでに起こりうる衝突が全て発生しないような組み合わせになっている確率」を計算し続ける問題に帰着できました。

向かい合う衝突だけを考慮した確率計算

まず簡単のため、向かい合う衝突だけを考慮します。「向かい合う向きであってはいけない」という2粒子間をUnion-Find等で連結することにすると、非連結な成分同士は独立に計算できるので、結局「連続するいくつかの粒子において、どの隣り合う2粒子間も RL の関係でない」という確率を求めれば良いことになります。

例えばインデックス $1, 2, 3$ の3粒子がこのような関係だとすると、衝突しないような向きの組み合わせは LLL, LLR, LRR, RRR の4通りです。その確率は

$S(1, 3) = (1-p_{1})(1-p_{2})(1-p_{3}) + (1-p_{1})(1-p_{2})p_{3} + (1-p_{1})p_{2}p_{3} + p_{1}p_{2}p_{3}$

と計算できます。上記のような計算を区間 $\lbrack l, r\rbrack$ について行った結果を $S(l, r)$ と表記することにします。

これを任意のインデックス区間について求めたいです。これは少しトリッキーなセグメント木を使って計算することができます。

それぞれの区間では、先ほどの $S(l, r)$ とともに

$L(l, r) = (1-p_{l})\cdots(1-p_{r})$
$R(l, r) = p_{l}\cdots p_{r}$

を持っておきます。区間 $\lbrack l, m\rbrack$ と区間 $\lbrack m+1, r\rbrack$ をマージする際には、

$L(l, r) = L(l, m)L(m+1, r)$
$R(l, r) = R(l, m)R(m+1, r)$
$S(l, r) = L(l, m)S(m+1, r) + S(l, m)R(m+1, r) - L(l, m)R(m+1, r)$

として計算できるため、これをマージ演算とするセグメント木で任意区間の計算結果を求めることができます。計算のイメージは以下の図のような感じ。

f:id:betrue12:20200107000152p:plain

Union-Findで連結成分を管理し、時刻 $t$ の時点での連結成分ごとの $S(l, r)$ の値を全て掛け合わせたものが $P(t)$ になります。

同じ向きでの衝突を考慮

同じ向きでの衝突を考慮するとさらに面倒になりますが、先ほどの延長で考えることができます。

同じ向きでの衝突が起こる時刻は向かい合う衝突が起こる時刻より遅いので、既に先ほどの連結成分となった区間に対して追加の条件が課されることになります。

以下の図を具体例として見てみます。

f:id:betrue12:20200107001541p:plain

LL や RR になってはいけない箇所があることで、先ほどの $S(l, r)$ の計算式のうち前の項・後ろの項がそれぞれ潰されます。つまり先ほどの連結成分に、前後どこまでの項が潰されているかの情報を追加で持たせればよいです。この生き残っている項の合計は、この図を例にすると $L(1, 1)S(2, 3)R(4, 5)$ と計算できるので、先ほどの延長で計算できます。生き残っている項がなくなった場合は衝突しない確率 $0$ 、つまり実験が必ず終了することを意味します。