AtCoder Regular Contest 032 C - 仕事計画

問題

　個の仕事があり、番目の仕事は時刻に始まりに終わる。時刻が重ならないようにできるだけ多くの仕事をこなすことを考えたとき、こなす仕事の種類を選び方が複数ある場合は辞書順最小のものとして構築せよ。

解法

　として後ろから求めていく。遷移は仕事を行わないときであり、仕事をこなすときは各仕事に対してそれを行ったときより多くの仕事がこなせるなら必ずそれを選び、同数になるなら辞書順最小のものを選ぶ、としていく。

反省

　昨日40分ほど考えて解けず、今日もまた40分ほど考えて解けず解説スライドを見て通した。

　想定解と似たような感じで各時刻についてを考えるというところには思い至っていたが、stringで経路を全て持とうとしてメモリが足りないことに(おそらく)なっていたり、前からdpしていくことしか考えていなかったので辞書順を上手く最小化するのがどうしても上手くいかなかった。

　forループDPを考えるときに順番を上手くやるのが苦手で、メモ化再帰で解きに行った方が可能性があったかもしれない。辞書順最小ということを考えなければ典型DPであり、なぜか典型はforループでやりたがってしまうという性質があるためそこに固執してしまった。

　解説を見てからも時刻から始まる仕事を行わないときの遷移が間違っていて2WAほど出してしまった。どうも遷移を考える丁寧さも足りず、全体的にDPは苦手という意識が強い。

コード

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

constexpr ll MAX = (ll)1e6;

int main() {
    ll N;
    cin >> N;
    struct Job {
        ll start, end;
    };
    vector<Job> jobs(N);
    for (ll i = 0; i < N; i++) {
        cin >> jobs[i].start >> jobs[i].end;
    }

    struct Edge {
        ll to, index;
    };
    vector<vector<Edge>> edges(MAX);
    for (ll i = 0; i < N; i++) {
        edges[jobs[i].start].push_back({ jobs[i].end, i });
    }

    struct Element {
        ll cost, next;
    };
    vector<Element> dp(MAX + 1, { 0, INT_MAX });

    for (ll i = MAX - 1; i >= 0; i--) {
        //時刻iから始まる仕事を行わない
        dp[i] = dp[i + 1];

        //時刻iから始まる仕事を行う
        for (Edge j : edges[i]) {
            ll new_cost = dp[j.to].cost + 1;
            if (dp[i].cost < new_cost) {
                dp[i].cost = new_cost;
                dp[i].next = j.index;
            } else if (dp[i].cost == new_cost) {
                dp[i].next = min(dp[i].next, j.index);
            }
        }
    }

    ll ans = dp[0].cost;
    cout << ans << endl;

    ll curr_time = 0;
    for (ll i = 0; i < ans; i++) {
        cout << dp[curr_time].next + 1 << " \n"[i == ans - 1];
        curr_time = jobs[dp[curr_time].next].end;
    }
}