AGC049
Bの1問ACでレートは+10、とりあえず水色はキープ
https://gyazo.com/92996ab7b886dd1c37392137f308c8fb
A
考えたこと
皆目見当がつかない
有向グラフでN=100
期待値を求める問題。期待値DP？
全部バラバラである時に2^100通りの状態ができてしまう
独立成分ごとに求めて和を取る？
公式解説
https://gyazo.com/b766b42c3b51dfb5c4c0a0df9f8f42c9
「操作回数」はこの表を横に足したもの
横に足すかわりに縦に足す
C
考えたこと
ボール1を0個、2を1個以下、kをk-1個以下にしたい
はみ出した分を削る？
それじゃ簡単すぎるか
はみ出した分を削るのでは最短ではない
「ロボットvが存在すれば」
あらかじめ壊しておけば丸ごと無効化できる
1つなボールを1つ大きい値に書き換えるだけで良い
そのボールを呼べば全部無効になる
これは十分条件なのでもっと削れる
既に他のロボットに壊されることが決まっている場合はカウントアップする必要がない
区間に覆われてるかの軽量な判定が必要
(先端, +1)と(末尾, -1)をリストに入れてソート
線形オーダーで累積和して非ゼロなら覆われている
→37WA
公式解説
よくわからない
Tweet
C:A≦Bのロボは a)Bを減らして0に到達できなくする b)右のロボを動かして壊す のどちらか。
aを使うのは高々1箇所。bのコストは1つあたり1。aで使うボールはbに再利用