読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

Codeforces Round #307 Div.2 C - GukiZ hates Boxes

問題

Codeforces Round #307(Div. 2) - C. GukiZ hates Boxes
一直線の列があり、列の各地点に箱の山が置かれている。箱が置かれている列の長さはnで、地点i(1<=i<=n)にはai個の箱が置かれているとする。この箱をm人で取り除きたい。各人は1秒に以下の2つの行動のどちらかができる。

  • 地点iからi+1に移動する
  • 地点iにある箱を1つ取り除く

最初、全員が地点0にいるとき、最小何秒で箱を取り除くことができるか。

制約

時間制限: 2秒
1 <= n, m <= 10^5
0 <= ai <= 10^9 (ただし、少なくとも1つの地点iでai != 0であることが保証されている)

解法

制約から、1秒ごとをシミュレーションする方法では間に合わない。
そこで、二分探索で解を探す。
ある時間以下で箱を全て取り除くことができるかについてであるが、各人について、

  • 現在、箱が残っている一番遠いところまで行く
  • 残りの時間で、今いる地点の箱を取り除けるだけ取り除く
    • まだ時間が余っている場合は、次に遠い場所の箱を取り除けるだけ取り除く
    • これを繰り返す

を行う。全ての人を使いきったときに、箱が全て取り除けていれば成功である。

知見

移動と箱を取り除く、という2つの行動を分けて考えるべきだった。
複数の行動があるときは、それを分けて考えられないかをまず考えてみるべき。
行動を分けて考えるべき類題: B: 直線塗り - AtCoder Regular Contest 040 | AtCoder

コード

上の問題は1-indexで書いたが、コードは0-indexで書いた