mayoko’s diary

プロコンとかいろいろ。

CODE FESTIVAL 2015 決勝 H - 焼肉の達人

全然自力で解けないんですが, それは…

解法

まず, 区間が 3 つ以上重なっている必要はないことがわかります。3 つ以上重なっている場合, それらを合わせた区間で左端にも右端にもならないものはあるだけ損になるからです。

で, このように 2 つしか重なる場所がないとわかると, 以下のようにコストを定義することで, 答えが M - コスト であるとわかります。
一つも重なっていない -> コスト 1
一つ重なっている -> コスト 0
2つ重なっている -> コスト 1
なので, あとはコストを最小化すれば良いです。頂点 0 から 頂点 M に向かうことを考えた時, S[i] -> S[i]+L[i] はコスト 0 で進むことができ, v -> v+1, v+1 -> v はコスト 1 で進むことが出来ると考えると, 上のコストを上手く表現しているので, このようなグラフを作ってダイクストラすれば解けます。

得た知見
  • 3 つ以上重なっちゃいけないことには気づいたけどその後が何もなかった
    • 全体 - コスト と考えて, コストを最小化する流れは最小カットとかに帰着するときも典型なので考えないとダメだった
      • それ考えればもしかすると思いついたかもな…
struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

const int MAXN = 100010;
int S[MAXN], L[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<vector<edge> > G(M+1);
    for (int i = 0; i < M; i++) {
        G[i].emplace_back(i+1, 1);
        G[i+1].emplace_back(i, 1);
    }
    for (int i = 0; i < N; i++) {
        cin >> S[i] >> L[i];
        G[S[i]].emplace_back(S[i]+L[i], 0);
    }
    auto d = dijkstra(M+1, G, 0);
    cout << M-d[M] << endl;
    return 0;
}