CROC 2016 - Elimination Round C. Enduring Exodus
問題概要
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 をカウントしないように注意。