AtCoder Grand Contest 049 A,B,C問題メモ

AtCoder Grand Contest 049

A - Erasing Vertices

• $N$ 頂点の単純有向グラフが与えられる
• 以下の操作を、全ての頂点が無くなるまで繰り返す
• 操作
  • 残っている頂点を1つ等確率で選ぶ
  • 選ばれた頂点を $v$ とすると、$v$ を含みそこから辺を伝っていける全ての頂点を削除する
• 操作回数の期待値を求めよ
• $1 \le N \le 100$

各頂点に対して「この頂点が操作対象として選ばれる確率」を求めて全て足すと、答えとなる。
いわゆる主客転倒。

その確率だが、$v$ から辺を逆に辿って到達できる頂点集合($v$ 含まず)を $P_v$ とすると、$P_v$ のどれかが $v$ より先に選ばれた時点で $v$ は削除され、操作対象でなくなる。

以下の言い換えを考えると

• $1～N$ の順列 $p_1～p_N$ を1つ固定し、この順に頂点を選んでいくとする
• $i$ 番目まで来たとき、頂点 $p_i$ が残っていれば1点加算、消えていれば何もしない
• 最終的な得点が、操作回数と一致する

順列の中で、$v$ と $P_v$ だけを取り出したとき、$v$ が先頭に来ていればよい。その確率は $\dfrac{1}{|P_v|+1}$ となる。

従って全体では $\displaystyle \sum_{i=1}^{N}\frac{1}{|P_i|+1}$ が答えとなる。

ただこの言い換え、競プロでたまに解法として使われるのを見るので正しいんだろうけど、 本来の操作（消された頂点がある中から逐次的にランダムに選ぶ）と、 果たしてちゃんと確率的に同じであることはどのように示せるのか、いまいちちゃんと理解できてない。

Python3

B - Flip Digits

• 長さ $N$ の、'0'と'1'からなる2つの文字列 $S,T$ が与えられる
• 以下の操作を $S$ に繰り返して $T$ と一致させられるか判定し、可能な場合は最小の操作手数を求めよ
• 操作
  • $S_i=1$ である好きな $i$ を選ぶ（$i \ge 2$）
  • $S_i=0$ とし、同時に $S_{i-1}$ を反転させる（0なら1、1なら0）
• $1 \le N \le 5 \times 10^5$

操作を解釈すると、

• 1つ手前が'0'である場合、'1'の位置を1つ手前にする
• 1つ手前が'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'が奇数個なら対消滅させられないので不可能。

そうでない場合可能で、回数は以下の合計となる

• $S_i$ の'1'を $T_j$ に持っていく場合、$j-i$
• $S_i$ と $S_j$ を対消滅させる場合、$j-i$

ただし上記の割り当て例は実際は不可能で、対消滅の過程で右端の'1'を左端まで持っていく必要があるが、残すべき'1'を挟んでいるので本来は移動できない。

ただ、求められているのは回数のみなので、ちょうどそこで移動させる対象が入れ替わったと考えてよく、操作回数には影響しない。

   ,--,
S  1001101  実際に操作可能な割り当て
    ,--'/     上記の実際には不可能な割り当てから求めた操作回数とは変わらない
T  0100100

Python3

C - Robots

• 数直線上にロボットがいる
  • 各 $i=0,1,2,...,\infty$ について、座標 $i$ にロボット $i$ が1台いる
• 整数が書かれたボールがある
  • 各 $i=1～N$ について、整数 $A_i$ が書かれたボールが $B_i$ 個ある
• 以下の操作を順番に行う
  • ボールに書かれた整数を、好きなだけ好きな正整数に書き換える
  • ボールを好きな順に食べる
  • ボールを食べる毎に、食べたボールに書かれた整数を $v$ とすると、
    • ロボット $v$ が生き残っていれば、1小さい座標に移動させる
    • 移動の結果、別のロボット $u$ がいたら、ロボット $u$ は破壊される
• 全てのボールを食べつつ、ロボット $0$ が破壊されないために、書き換える必要のあるボールの最小数を求めよ
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i,B_i \le 10^9$

いくつか、問題文の条件を洗い出す。

ボールを食べる順によってロボット0を破壊しうるロボットをダメロボット、 破壊しえないロボットを安全ロボットとする。

• 初期状態のダメロボットは、$A_i \le B_i$ であるロボット $A_i$
• ロボット0の破壊を回避するには、以下の2手段がある
  • ダメロボットを自身より番号の大きい安全ロボットに破壊してもらう
  • ダメロボットのボールを書き換えて $A_i \gt B_i$ にして安全ロボットにする

破壊してもらうロボットがまたダメロボットだと、 どっちみちそいつを破壊するロボットが必要になり意味が無いので、 破壊するロボットは安全ロボットである必要がある。

その上でいくつか例を作ると、

自分より後ろの安全ロボットが自分まで届くようにボールを移動させる
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

これらを踏まえて、座標の大きい方から、以下の情報を管理しながらボールを見ていく。

• $s$: ここまでの安全ロボットが破壊してくれる最小座標
• $t$: ここまでの全てのダメロボットを破壊するために、安全ロボットのボールを増やす必要のある個数
• $ans$: ここまでの暫定答え

• $A_i$ と $A_{i+1}$ が離れている場合
  • 自身より1大きい座標に(隠れた)安全ロボットがいるので、最小座標を更新する
  • $s←\min(s,A_i+1)$
• 初期状態で安全ロボットの場合
  • 最小座標を更新できるならする
  • $s←\min(s,A_i-B_i)$
• 初期状態でダメロボットの場合
  • 自身を安全ロボットにする場合
    • $B_i-A_i+1$ 個減らす
    • それ以下については書き換えなくてよくなる
    • 書き換える必要のある総個数は増やす個数と減らす個数の大きい方
    • $ans←\min(ans,\max(t, B_i-A_i+1))$
  • 自身を破壊してもらう場合
    • $s \le A_i$ なら何もしなくても破壊できる
    • $s \gt A_i$ なら、追加で安全ロボットのボールを増やす必要がある
      • $t += s-A_i$

ここまでの $ans$ は、ダメロボットのどれかを安全ロボットにするパターンしか考慮されていないが、 全て破壊してもらうパターンもあるので更新する

• $ans ← \min(ans,t)$

これで答えが $O(N)$ で求まる。

Python3

D - Convex Sequence

Python3