AtCoder Beginner Contest 174を見直す E - Logs

問題

n本の丸太があり、それぞれの長さが数列で与えられます。
これらの丸太をk回まで切ることができます。最も長い丸太の長さが最小になるように切った場合の長さを求め、小数点以下を切り上げた値で出力してください。

素直に考えると、丸太の中で最も長いものを切るというのを繰り返すと良さそう。その場合１本の丸太に対して複数回切る場合にちょっと注意が必要で、１回目切るときには半分にして、２回目切るときには一旦元の長さに戻して三等分しないと最適にならないです。

ただ、制約で丸太の本数nが「2*10^5」、切る回数kが「10^9」となっているので、この方法だとO(nk)となり「TLE」になるのは明らかです。

解説を見て作成した解答

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using vi = vector<int>;

int main() {
   int n, k;
   cin >> n >> k ;
   vi a(n);
   rep(i, n) cin >> a.at(i);
   //二分探索
   int l = 0, r = 1e9;
   while(r-l > 1) {
       int x = (l+r)/2;
       auto f = [&](int x) {
           ll now = 0;
           //丸太を切る回数を求める
           rep(i, n) now += (a.at(i)-1)/x;
           return now <= k;
       };
       if (f(x)) r = x; else l = x;
   }
   cout << r << endl;
   return 0;
}

1e9は10^9と同じ意味です。

説明してみる

逆に、最も長い丸太をxにするためには何回切らないといけないかを考える。例えば、最も長い丸太を2にするためには以下のように6回切る必要がある。

あとは、以下のような感じで長さ毎に切る回数がk回以下（OK）か、kより真に大きいか（NG）かの二部探索をすれば良いです。

今回は、切る回数がk回以下で最も小さい値を知りたいので、上図のようにOK（k回以下で達成できる）とNG（k回以下では達成できない）の境界線を求めます。

ほぼ、解説動画のなぞった感じですが、次に似たような問題が出たら解ける。可能性はないとは言い切れないです！