各頂点に対して「この頂点が操作対象として選ばれる確率」を求めて全て足すと、答えとなる。
いわゆる主客転倒。
その確率だが、$v$ から辺を逆に辿って到達できる頂点集合($v$ 含まず)を $P_v$ とすると、$P_v$ のどれかが $v$ より先に選ばれた時点で $v$ は削除され、操作対象でなくなる。
以下の言い換えを考えると
順列の中で、$v$ と $P_v$ だけを取り出したとき、$v$ が先頭に来ていればよい。その確率は $\dfrac{1}{|P_v|+1}$ となる。
従って全体では $\displaystyle \sum_{i=1}^{N}\frac{1}{|P_i|+1}$ が答えとなる。
ただこの言い換え、競プロでたまに解法として使われるのを見るので正しいんだろうけど、 本来の操作(消された頂点がある中から逐次的にランダムに選ぶ)と、 果たしてちゃんと確率的に同じであることはどのように示せるのか、いまいちちゃんと理解できてない。
操作を解釈すると、
なので、'1'の数は増やせないし、手前にしか移動できないし、2個ずつしか消せない。
それを踏まえると、$T$ にある'1'は、$S$ での直近の右の'1'を持ってくると見なせば、操作回数で損しないことが言える。
その場合、使われなかった $S$ の'1'は2個ペアで対消滅させる。
,-----, ←残りの'1'を対消滅 S 1001101 / | T 0100100
$T_i~T_N$ の'1'の個数の方が $S_i~S_N$ より多くなる $i$ があれば不可能。
また、残りの'1'が奇数個なら対消滅させられないので不可能。
そうでない場合可能で、回数は以下の合計となる
ただし上記の割り当て例は実際は不可能で、対消滅の過程で右端の'1'を左端まで持っていく必要があるが、残すべき'1'を挟んでいるので本来は移動できない。
ただ、求められているのは回数のみなので、ちょうどそこで移動させる対象が入れ替わったと考えてよく、操作回数には影響しない。
,--, S 1001101 実際に操作可能な割り当て ,--'/ 上記の実際には不可能な割り当てから求めた操作回数とは変わらない T 0100100
いくつか、問題文の条件を洗い出す。
ボールを食べる順によってロボット0を破壊しうるロボットをダメロボット、 破壊しえないロボットを安全ロボットとする。
破壊してもらうロボットがまたダメロボットだと、 どっちみちそいつを破壊するロボットが必要になり意味が無いので、 破壊するロボットは安全ロボットである必要がある。
その上でいくつか例を作ると、
自分より後ろの安全ロボットが自分まで届くようにボールを移動させる Ai 3 4 5 Bi 100 100 1 ↓ Ai 3 4 5 Bi 99 100 2
入力に無いAiにも安全ロボットがいることに留意する Ai 3 4 5 Bi 100 100 100 ↓ Ai 3 4 5 6 Bi 99 99 99 3
Biを減らすことで安全ロボットにしたダメロボットは、 自分より座標の小さい全てのダメロボットを破壊できる最強の安全ロボットになり、 座標Ai未満については書き換える必要がなくなる Ai 3 4 5 6 Bi 100 100 100 7 ↓ Ai 3 4 5 6 Bi 100 100 100 5 あと2個はどこか適当に △ ¥ ▲ ( ㊤ 皿 ㊤) がしゃーん ( ) /│ 肉 │\ がしゃーん < \___/ > ┃ ┃ = = 最強の安全ロボだよ 自動でダメロボットを破壊してくれるすごいやつだよ
ダメロボットを安全ロボットにするために書き換えるボールは、 より座標の大きい安全ロボットを進ませるのに流用できる Ai 3 4 5 6 9 10 11 13 15 Bi 100 100 100 8 100 100 100 2 100 ↓ ↓ ↓ ↓ Ai 3 4 5 6 9 10 11 13 15 16 Bi 100 100 100 5 100 100 100 4 100 1
これらを踏まえて、座標の大きい方から、以下の情報を管理しながらボールを見ていく。
ここまでの $ans$ は、ダメロボットのどれかを安全ロボットにするパターンしか考慮されていないが、 全て破壊してもらうパターンもあるので更新する
これで答えが $O(N)$ で求まる。