Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 314 F問題 A Certain Game

AtCoder ABC ABC314 F問題 475 pts

問題
提出解答
解法

問題

提出解答

解法

「データ構造をマージする一般的なテク」を利用して, この問題を解く.

以下のものを用意する.
- $1,2, \dots, N$ を頂点に持つ Union-Find $U$ .
- に対して, とする.
  - $\Gamma_x$ は頂点 $x$ を代表元に持つ連結成分におけるベースとなる期待値を記録する.
  - $\delta_x$ は $x$ が属する連結成分の代表元を $y$ としたときの $\Gamma_y$ と, その時点での勝利回数の期待値との差を記録する.
- $i=1,2,\dots, N$ に対して, $V_i$ を $i$ の一要素のみからなるリストとする.
の順に以下を行う.
- $U$ において, $p_i$ が属する連結成分の頂点数が, $q$ に属する連結成分の頂点数より大きいならば, $p,q$ を入れ替える.
- $p_i, q_i$ を $U$ における $p_i$ の代表元, $q_i$ における代表元に置き換える.
- $U$ において, $p_i, q_i$ が属する連結成分の頂点数をそれぞれ $a,b$ とする.
- $V_p$ の各頂点 $y$ について, $\delta_y$ に $\displaystyle \Gamma_{p_i} - \Gamma_{q_i} - \frac{b-a}{a+b}$ を加算する.
- $\Gamma_{q_i}$ に $\dfrac{b}{a+b}$ を加算する.
- $V_{q_i}$ に $V_{p_i}$ の全ての要素を付け加える.
- $U$ において, $p_i, q_i$ を併合する.

最後に残る唯一の連結成分の代表現を $z$ としたとき, $i=1,2, \dots, N$ のそれぞれに対する正解は, $\Gamma_z+\delta_i$ である.