Codeforces Round #200 (Div. 1) C. Read Time

B よりこっちのほうがアイデアは簡単(実装は面倒)に感じました。

問題

Codeforces

解法

動かしても良い距離 x を決めると, それぞれの disk head をどう動かせばよいのかを貪欲に求めることができるので, x に関して 2 分探索すれば良いです。

const int MAXN = 100010;
int n, m;
ll h[MAXN], p[MAXN];

bool ok(ll x) {
    int cur = 0;
    int tar = 0;
    while (1) {
        if (tar == m) return true;
        if (cur == n) break;
        while (cur < n && abs(h[cur]-p[tar]) > x) cur++;
        if (cur == n) return false;
        if (h[cur] >= p[tar]) {
            int j = tar+1;
            while (j < m && p[j] <= h[cur]) j++;
            if (j == m) return true;
            ll y = max(x-2*(h[cur]-p[tar]), (x-(h[cur]-p[tar]))/2);
            ll now = h[cur];
            while (j < m && y >= 0) {
                y -= p[j]-now;
                now = p[j];
                if (y >= 0) j++;
            }
            tar = j;
        } else {
            int j = tar+1;
            while (j < m && p[j] <= h[cur]+x) j++;
            tar = j;
        }
        cur++;
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < m; i++) cin >> p[i];
    ll low = -1, high = 1ll<<60;
    while (high - low > 1) {
        ll med = (high+low) / 2;
        if (ok(med)) high = med;
        else low = med;
    }
    cout << high << endl;
    return 0;
}