AtCoder Beginner Contest 144 F - Fork in the Road
https://atcoder.jp/contests/abc144/tasks/abc144_f
問題文には書いていないが制約に書いてある $s_i < t_i$ という条件から与えられるグラフは閉路を持たないことが分かる。この性質を使えば動的計画法によって期待値を求められる。それは以下の式によって得られる。
\begin{align}
E_i = \frac{1}{|N(i)|} \sum_{ j \in N(i)} (E_j + 1)
\end{align}
この式を計算するには $O(M)$ 掛かるため、ある辺を消してみて再び求めなおすと $O(M^2)$ 掛かってしまう。ここで諦めずに、ある辺を消してみて再び求めなおす処理をもっと速く行えないか考えてみよう。実は適切な前計算をしておくと辺一本あたり $O(1)$ で再計算できる。
辺 $(a,b)$ を消したときの期待値の変化量 $E_1' - E_1$ に着目する。実はこの変化量は $E_a' - E_a$ の変化量に比例する。これは上で書いた式の線形性に基づく。よってこの比例定数さえ知っていれば $E_1'-E_1$ は $E_a'-E_a$ から知ることができる。この比例定数を求める最も単純な方法は $E_a=1$ として上に書いた式を計算することだろう。計算し終えたときの $E_1$ が比例定数になっている。これを各頂点に対して行えば合わせて $O(NM)$ 掛かる。これでこの問題は解くことができるが比例定数を求める部分はもっと高速にできて $E_1=1$ として辺を逆向きに上記の計算をすればいい。よく考えると同じものを求めていることが分かるので、これで計算量 $O(M)$ になる。
このグラフが閉路を持たないことは次のように確かめられる。閉路が $v_1, v_2, \ldots, v_n, v_1$ があるならば矛盾することを示す。このときこのグラフの性質から $v_1 < v_2 < \cdots < v_n < v_1$ であり $v_1 < v_1$ となる。$v_1 < v_1$ かつ $v_1 \ge v_1$ より矛盾する。
この性質を持つような頂点の並べ方がトポロジカルソートであり、トポロジカルソートができるグラフは閉路を持たない、ということを知っていれば閉路を持たないことがすぐに分かるかもしれない。問題文に書いてくれていても良さそうな気がするが、引っかかったことで印象が強くなったと思えば悪くはなかったのかもしれない。
The problem statement doesn't say this graph is a DAG, but we can prove that this graph is a DAG. So we can solve this problem by using DP. The update formula is as follows.
\begin{align}
E_i = \frac{1}{|N(i)|} \sum_{ j \in N(i)} (E_j + 1)
\end{align}
We need O(M) time to calculate this formula, so straight forward solution takes O(M^2) time. We shouldn't give up at this point, this approach can be faster than $O(M)$ per edge. That is, O(1) algorithm exists.
Focus on the difference $E_1' - E_1$ when edge (a,b) is removed. Actually, this difference $E_1' - E_1$ is proportional to the difference $E_a' - E_a$. So if we already know the proportionality constant, we can easily obtain the new answer from $E_a' - E_a$. The easiest way to calculate the constant is to use the recurrence relation similar to the above formula. Needless to say, its requires $O(NM)$ in total, which is fast enough in this problem. However, we can speed up this solution more efficiently by doing similar DP on the reversed graph. I won't explain the details, but I believe that you can understand it by yourself. The true time complexity is only $O(M)$.
