codefestival2015予選A D問題 作成した二分探索のコードが通らない

Question

前提

atcoder上のこちらの問題についての質問です。下のコードで問題を解こうとしたのですが、すべてACになりません。方針としては解説にある通り、左側の車両を貪欲的に埋めていく方針です。どこに漏れがあるのかご指摘いただけると幸いです。よろしくおねがいします。

該当のソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

int N, M;
vector<ll> X;

bool C(ll t){
    vector<int> D(M); // 作業員iが担当できる右端の座標
    for(int i = 0; i < M; ++i){
        ll l, r;  //l...前の作業員が担当した電車の座標
        if(i == 0){
            l = 0;
        }else{
            l = D[i - 1];
        }
        ll L = X[i] - l - 1; //L...左側への移動距離
        if(t < L) return false;
        r = min(X[i + 1] - 1, max(t - 2 * L + X[i], (t - L) / 2 + X[i]));
        D[i] = r;
    }
    return D[M - 1] >= N;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    X.resize(M);
    for(int i = 0; i < M; ++i){
        cin >> X[i];
    }
    sort(X.begin(), X.end());
    ll lb = -1, ub = 3e10;
    while(ub - lb > 1){
        ll mid = (lb + ub) / 2;
        if(C(mid)) ub = mid;
        else lb = mid;
    }
    cout << ub << endl;
}

Answer 1

//22行目
 r = min(X[i + 1] - 1, max(t - 2 * L + X[i], (t - L) / 2 + X[i]));

for文の最終ループではi == M - 1なので、X[i + 1] == X[M]となり、配列外参照をしてしまっています。
i == M - 1の場合はX[i + 1] - 1ではなくNとの最小値を取るか、最小値は取らずにr = max(...);とすればよいです。

あとは、オーバーフローの可能性があるので配列Dの型は一応vector<ll>にしておくと良いでしょう。

Comments

[rdld036]

無事解決できました。ご指摘ありがとうございます。