AtCoder Regular Contest 026 C - 蛍光灯

問題

　西側 $0:$ メートル地点から東側へ $L$ メートル分の廊下がある。この廊下には $N$ 個の蛍光灯が付いており、 $i$ 番目の蛍光灯は $l_i$ 地点から $r_i$ 地点の間を照らすことができ、点けるのに $c_i$ 円の費用がかかる。廊下をすべて照らすときの最小費用を求めよ。

解法

　まず蛍光灯を左端の値でソートする。 $i$ 番目の蛍光灯を使うときは、それまでの蛍光灯で $i$ 番目の蛍光灯の左端から右端までの間のどこかに照らすコストの最小値が来ているはずである。これはセグメント木を用いれば $O(\log{N})$ で求めることができる。そして最小コストを $i$ 番目の蛍光灯の右端の位置に記録すれば、それ以降の蛍光灯でそこを含むものがその最小コストを拾うことができる。

別解

　各地点をノードとし、蛍光灯のエッジを張る。また戻る向きで隣のノードへはコスト0で行けるものとしてさらにエッジを張ると地点0から地点Lまで行く最短経路問題に帰着する。賢い。

　creep04のコード

反省

　1時間17分(3WA)でAC。16分ほどで部分点解法はわかったが、そこから計算量を落とす方法がわからなかった。部分点解法として考えたのが更新を範囲で行い、値の取得を点で行うようなDPであったため、それをそのままセグメント木に落とそうとすると遅延評価セグメント木となり、いろいろなサイトを調べて実装してみたがバグを取り切れなかった。

　結局1時間ほどたってから解説スライドを見たところ、更新を点で行い値の取得を範囲で行っても解けるとのことだった。これであれば素直なセグメント木を使って解くことができるため、実装でもバグりにくいのだろう。その方針で(セグメント木はコピペして)書いて通した。

　たまたまcreep04の提出も見てみたらダイクストラ法で解いていて目から鱗だった。問題で使われるモチーフが橋とかだったらこれにもすぐ気づけたりするんだろうか。本質が見えていない証拠である。

コード

#include"bits/stdc++.h"
#include<random>
using namespace std;
using ll = int64_t;

constexpr ll INF = LLONG_MAX / 2;

//http://tsutaj.hatenablog.com/entry/2017/03/29/204841 のコピペ(一部改変)
struct SegmentTree {
private:
    ll n;
    vector<ll> node;

public:
    // 元配列 v をセグメント木で表現する
    SegmentTree(vector<ll> v) {
        // 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
        // セグメント木全体で必要なノード数は 2n-1 個である
        ll sz = v.size();
        n = 1; while (n < sz) n *= 2;
        node.resize(2 * n - 1, INF);

        // 最下段に値を入れたあとに、下の段から順番に値を入れる
        // 値を入れるには、自分の子の 2 値を参照すれば良い
        for (ll i = 0; i < sz; i++) node[i + n - 1] = v[i];
        for (ll i = n - 2; i >= 0; i--) node[i] = min(node[2 * i + 1], node[2 * i + 2]);
    }
    void update(ll x, ll val) {
        // 最下段のノードにアクセスする
        x += (n - 1);

        // 最下段のノードを更新したら、あとは親に上って更新していく
        node[x] = min(node[x], val); //ここでminを取る処理を入れないとサンプルが合わない<------------改変部分
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = min(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    
    // 要求区間 [a, b) 中の要素の最小値を答える
    // k := 自分がいるノードのインデックス
    // 対象区間は [l, r) にあたる
    ll getmin(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        // 最初に呼び出されたときの対象区間は [0, n)
        if (r < 0) r = n;

        // 要求区間と対象区間が交わらない -> 適当に返す
        if (r <= a || b <= l) return INF;

        // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
        if (a <= l && r <= b) return node[k];

        // 要求区間が対象区間の一部を被覆 -> 子について探索を行う
        // 左側の子を vl ・ 右側の子を vr としている
        // 新しい対象区間は、現在の対象区間を半分に割ったもの
        ll vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};

int main() {
    ll N, L;
    cin >> N >> L;
    struct Light {
        ll l, r, c;
        bool operator<(const Light& rhs) const {
            return l < rhs.l;
        }
    };
    vector<Light> lights(N);
    for (ll i = 0; i < N; i++) {
        cin >> lights[i].l >> lights[i].r >> lights[i].c;
    }

    sort(lights.begin(), lights.end());

    vector<ll> cost(L + 1, INF);
    cost[0] = 0;
    SegmentTree st(cost);

    for (ll i = 0; i < N; i++) {
        ll pre_cost = st.getmin(lights[i].l, lights[i].r + 1);
        ll new_cost = pre_cost + lights[i].c;
        st.update(lights[i].r, new_cost);
    }

    cout << st.getmin(L, L + 1) << endl;
}