CROC 2016 - Elimination Round C. Enduring Exodus

codeforces.com

問題概要

n 個の部屋が一列に並んでおり、その部屋が空いているかどうかの情報が与えられる。

John と k 頭の牛を各部屋に割り当てたいが、このとき John から最も離れた牛との距離はできるだけ小さくしたい。

John と最も離れた牛との距離の最小値はいくつになるだろうか。

解法

John を部屋 i に割りあてたとき、John との距離が x の範囲に k 頭の牛を配置できるかを二分探索すればいい。

区間 [i-x,i-1] と区間 [i+1,i+x] にある 0 の個数が k 以上なら配置可能である。0 の個数は累積和を使えば O(1) で求められる。

CROC 2016 - Elimination Round C. Enduring Exodus

位置 i の 0 をカウントしないように注意。