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