AGC049 C - Robots (800)
コンテスト中の考察
$ A_i - B_i \gt 0ならそのまま動かしてしまって良い
$ A_i - B_i \le 0だとそのまま動かすとロボット0に到達してしまうので以下のどちらかが必要
$ A_i - B_i = 1となるように$ B_iを減らす
他のロボットに壊してもらう
$ A_i - B_i \gt 0について先に移動先を求めておく
移動元と移動先の間のロボットについては何もしなくても勝手に壊されてくれる
これを全てのロボットで愚直に計算すると$ O(N^2)になるのでいもす法でまとめて計算する
全てのボールについて右から順に以下を行う
上で移動させたボールについては飛ばす
答えを$ \max(これまでの移動の和, B_i - A_i + 1)で更新する
$ A_i - B_i = 1となるように更新すればここより左のボールは全て壊されるので考えなくて良い
和が今回減らす量より多いならば今までの移動をできるだけ今回減らした分から使ったことにできる
和が今回減らす量より少ないならば今までの移動を全て今回減らした分の一部から使ったことにできる
自動的に壊れないロボットのボールなら以下を行う
ここより右で最も近い移動済みのロボットを見つける
そのロボットを今回減らす分で左側に動かす
今の地点を越えないようにする
減らした分を移動の和に足す
そのようなロボットがいないなら$ A_i - B_i = 1となるように更新するしかないのでそのようにして終わり
サンプルがほとんど落ちてWA
コンテスト後の考察
ある番号のロボットを壊すには1つ右隣に1個ボールを置くだけで良いのでそこを直したらAC
$ N個のロボットの移動先を求めるのが$ O(N \log N)、$ N通りの最前を求めるのが$ O(N)