ひらめの日常

プログラミングと読書と

AtCoder: ABC128-E Roadwork (500)

Roadwork

問題はこちら

atcoder.jp

考え方

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

  •  s_i - x_i \leq d_j \lt t_i - x_i

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

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

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

  • setでスタート時間  d_1, ..., d_j, ..., d_Q を管理する。
  • まず通行止区間を全て調べるので、ここに  O(N)
  • 各通行止区間について、 s_i - x_i \leq d_j となるような  d_jlower_bound で見つける。ここに  O(log(Q))
  •  d_j \lt t_i - x_i となっている限り、set からスタート時間を削除し、 d_j にスタートした人の答えは  x_i となる。ここは最大でも Q 回までしか回ることはない。要素の削除には  O(log(Q))

以上より、合計の計算量は  Nlog(Q) + Qlog(Q) = (N+Q)log(Q) になる。

具体的な実装

  • structのvectorとして、 s, t, x を管理。 x の昇順にsortする。
  • 各スタート時間とindexのpairを、setにいれて管理。
  • それぞれの通行止区間について、 s_i - x_i \leq d_j \lt t_i - x_i を満たすような  d_j があれば、setからeraseする。
    • この時、別に答え出力用のanswer配列を用意しておき、answer[index] x_j を代入する。
  • 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