難易度 8 でもおかしくないと思った。
B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね...

問題へのリンク

問題概要

$N$ 個の工場がある。各工場は座標 $A_{i}$ ( $0 \lt A_{1} \lt \dots \lt A_{N}$ ) にあって、作業量が $B_{i}$ となっている。

$K$ 人の作業員がいる。時刻 0 にはすべての人が座標 0 で待機している。各人は

1 秒で 1 の作業ができる (どの工場においても)
1 秒で 1 だけ移動できる

すべての工場のすべての作業が完了するのに要する時間の最小値を求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le K, A_{i}, B_{i} \le 10^{9}$

考えたこと：二分探索っぽい

それぞれの作業員の行動過程はかなり複雑なものになりうる。しかし冷静に考えると、すべての作業時間の総和は

移動時間の総和 (これは一定ではない)
作業時間の総和 (これは一定)

の総和となる。つまり、「移動時間の総和」をなるべく小さくしたいのだ。しかし、最奥の工場に送り込む人数が少なすぎると、その人の作業完了までの時間がボトルネックになってしまう。このように

全員の作業時間を均一化した上で
すべての作業を完了したい

というシチュエーションは、二分探索が有効だと相場は決まっている。「最大値の最小化」において二分探索が有効なのと原理は一緒。

「全員の作業時間を $x$ 秒以内にできるか」

という判定問題を解くことになるのだが、この $x$ を固定することで初めて、"バランス" (今回は奥の工場に送り込む人数が多いと移動時間が無駄で、少ないと奥工場での作業がネックになる...というトレードオフがある) をとるための最適戦略を決められるのだ。

奥の工場から片付けていく

ここまでの考察で、もうほとんど解けている。奥の工場から順番に考えていこう。

全員の作業時間を $x$ 秒以内にしたいという制約条件の下では、最奥の工場へと送り込むべき人数が決まる。その人たちは、途中の工場へと寄り道せず、一心不乱にまず最奥の工場へと向かう (最後の一人だけ例外)。その時点で、最奥の工場で費やせる時間が決まる ( $x - (移動時間)$ )。よって、最奥へと送り込む人数の最小値が求められる。最後の一人だけは時間が余るので、その分は最奥から 2 番目の工場に割り当てれば OK。

こうして、最奥の工場から始めて、奥から 2 番目、3 番目、4 番目の工場へと送り込む人数が順に Greedy に決まっていく。 $K$ 人で全工場の作業を終えられれば "Yes"、終えられなければ "No" だ。

計算量は、判定問題は、 $O(N)$ で解けるので、座標と作業量の総和を $V$ として $O(N \log V)$ の計算量で解ける。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[N-i-1];
    for (int i = 0; i < N; ++i) cin >> B[N-i-1];

    auto judge = [&](long long x) -> bool {
        long long sum = 0, amari = 0;
        for (int i = 0; i < N; ++i) {
            if (amari >= B[i]) {
                amari -= B[i];
                continue;
            }
            long long work = B[i] - amari;
            long long each = x - A[i];
            if (each <= 0) return false;
            long long num = (work + each - 1) / each;
            sum += num;
            amari = each * num - work;
        }
        return sum <= K;
    };

    long long left = 0, right = 1LL<<60;
    while (right - left > 1) {
        long long x = (left + right) / 2;
        if (judge(x)) right = x;
        else left = x;
    }
    cout << right << endl;
}