mayoko’s diary

プロコンとかいろいろ。

CODE FESTIVAL 2015 予選A D - 壊れた電車

AtCoder

CODE FESTIVAL 2015 予選A に参加しました。なんとか全完, 29 位で予選通過できそうです。良かった…
D 問題は過去のこどふぉに(全く同じと言っていいほど)似た問題が出てますね


問題

code-festival-2015-quala.contest.atcoder.jp

解法

回数を二分探索します。

回数 x が決まると, それぞれの整備士がどう動くべきかは貪欲に決まります。
まず, 左端の整備士は左端をカバーしつつできるだけ右側まで整備するのが最適です。で, 左端から 2 番目の整備士は一番左端の人がカバーできなかった一番左端のところからできるだけ右側まで整備するのが最適です。...という感じでできるだけ左端を右側に押し上げるように整備士が動いてくれるように調整します。

注意すべき点は,

  • 上限は 1.5N であること(真ん中に一人整備士が置かれた場合)
  • 整備士の最適な動きは,
    • 左端をカバー -> できるだけ右側に行く または できるだけ右側に行く -> 左端をカバー のいずれか

という点でしょうか。どちらも本番引っかかりました(特にひとつ目は気づくのに時間かかった。前こどふぉで解いたのに)。

const int MAXM = 100010;
const int MAXN = 1e9+7;
ll X[MAXM];
ll N;
int M;

bool ok(ll x) {
    ll l = 0;
    for (int i = 0; i < M; i++) {
        ll num = X[i]-l;
        if (num > x) return false;
        if (num <= 0) l = X[i]+x+1;
        else {
            ll tmp = X[i]-2*num+x;
            tmp = max(tmp, X[i]+(x-num)/2);
            l = tmp+1;
            l = min(N, l);
        }
    }
    return l >= N;
}

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