AtCoder: ABC128-E Roadwork (500)

Roadwork

問題はこちら

atcoder.jp

考え方

まずは、 に出発した人がどのような条件を満たした時に の地点で通行止に引っかかるかを考えてみる。すると、1秒ごとに1進むので、以下の条件を満たしているときに通行止に引っかかるということが分かる。

• 

これを愚直にやると、 箇所の通行止について、 人の出発時間を調べるので のオーダーになり制限時間に間に合わない。

そこで、 各々の通行止区間について、そこで止まるものを取り除く という風に考えてみる。具体的には、一番手前で止まった場合はもうそれ以降の区間について考える必要がないので、調べる集合から取り除くことができるという考え。

なぜこれを行うと間に合うのか？

• setでスタート時間 を管理する。
• まず通行止区間を全て調べるので、ここに 。
• 各通行止区間について、 となるような を lower_bound で見つける。ここに 。
• となっている限り、set からスタート時間を削除し、 にスタートした人の答えは となる。ここは最大でも 回までしか回ることはない。要素の削除には 。

以上より、合計の計算量は になる。

具体的な実装

• structのvectorとして、 を管理。 の昇順にsortする。
• 各スタート時間とindexのpairを、setにいれて管理。
• それぞれの通行止区間について、 を満たすような があれば、setからeraseする。
  • この時、別に答え出力用のanswer配列を用意しておき、answer[index] に を代入する。
• answerを出力する。

解答

抜粋部分

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

struct stx {
    ll s, t, x;

    stx(ll s, ll t, ll x) : s(s), t(t), x(x) {}
};

int main() {
    ll n, q;
    cin >> n >> q;
    vector<stx> v;
    rep(i, n) {
        ll s, t, x;
        cin >> s >> t >> x;
        stx temp(s, t, x);
        v.emplace_back(temp);
    }
    set<pair<ll, ll>> set1;
    rep(i, q) {
        ll d;
        cin >> d;
        set1.insert(pair<ll, ll>(d, i));
    }
    auto comp = [](stx &a, stx &b) {
        if (a.x == b.x) {
            if (a.s == b.s) return a.t < b.t;
            return a.s < b.s;
        }
        return a.x < b.x;
    };
    sort(v.begin(), v.end(), comp);

    vector<ll> ans(q, -1);
    rep(i, n) {
        ll s = v[i].s, x = v[i].x, t = v[i].t;
        auto it = set1.lower_bound(pair<ll, ll>(s - x, -1));
        while (it != set1.end()) {
            if (t - x <= it->first) break;
            ans[it->second] = x;
            set1.erase(it++);
        }
    }
    rep(i, q) cout << ans[i] << endl;
    return 0;
}

Submission #6087534 - AtCoder Beginner Contest 128