(強連結成分分解・DP)ARC-030-C-有向グラフ

問題URL→http://arc030.contest.atcoder.jp/tasks/arc030_3

昔コンテストで見て解けないまま放っておいた問題。
強連結成分分解とDPの複合問題。というか強連結成分分解単体を問われる問題はなさげ。

この方のコードを参考にさせていただいた。すごく読みやすい。
http://arc030.contest.atcoder.jp/submissions/1511810

コードを写経したは良いがまだ完全には理解できていないので、復習する。

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) for(ll i=1;i<=(n);i++)
#define MOD 1000000007
#define int long long
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
using namespace std;
typedef long long ll;
const int INF = 1e9;

int N;  //頂点数
int M;  //辺の数
int K;  //回収するアルファベットの数
char C[300];    //頂点に書かれているアルファベット
vector<int> G[300]; //グラフの辺
vector<int> R[300]; //グラフの逆辺
vector<int> G2[300];

bool used[300];
vector<int> vs; //帰りがけ順の並び
int ord[300];   //属する強連結成分のトポロジカル順序
string T[300];

void dfs(int x)
{
    if (used[x]) return;
    used[x] = true;
    for (int t : G[x]) dfs(t);
    vs.push_back(x);
}

void rdfs(int x, int k) {
    if (used[x]) return;
    used[x] = true;
    ord[x] = k;
    for (int t : R[x]) rdfs(t, k);
}

int scc()
{
    REP(i,N) used[i] = false;
    REP(i,N) dfs(i);
    REP(i,N) used[i] = false;
    int k = 0;
    for (int i=vs.size()-1; i>=0; i--) {
        if (!used[vs[i]]) rdfs(vs[i], k++);
    }
    return k;
}

string memo[300][301];
string dp(int x, int k)
{
    if (memo[x][k] != "") return memo[x][k];
    if (k == 0) return "";

    int len = T[x].length();
    string m = "~";
    for (int d=0; d<=min(len,k); d++) {
        string prefix = T[x].substr(0, d);
        string e = "~";
        if (k == d) e = "";
        else {
            for (int t : G2[x]) {
                string o = dp(t, k - d);
                if (o != "~") e = min(e, o);
            }
        }
        if (e != "~") m = min(m, prefix + e);
    }

    return memo[x][k] = m;
}

signed main()
{
    cin >> N >> M >> K;
    REP(i,N) cin >> C[i];
    REP(i,M) {
        int a, b;   //頂点aから頂点bに移動できる辺がある
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        R[b].push_back(a);
    }

    int V = scc();  //強連結成分分解。Vは強連結成分の個数
    REP(i,V) {
        string s = "";
        REP(x,N) if (ord[x] == i) s += C[x];
        sort(s.begin(), s.end());
        T[i] = s;
    }
    REP(x,N) {
        for (int t : G[x]) {
            if (ord[x] != ord[t]) G2[ord[x]].push_back(ord[t]);
        }
    }
    REP(i,V) {
        sort(G2[i].begin(), G2[i].end());
        uniq(G2[i]);
    }

    string s = "~";
    REP(i,V) s = min(s, dp(i, K));
    if (s == "~") s = "-1";
    cout << s << endl;
}

(区間スケジューリング・辞書順最小)ARC-032-C-仕事計画

問題URL→http://arc032.contest.atcoder.jp/tasks/arc032_3

問題概要
区間スケジューリング問題で辞書順最小の選び方を求め、さらに経路復元させる問題。
区間スケジューリングのDP解法に仕事の番号を持たせてDPする。
他の人のコードを見た。multimap初めて使った。
multimapはlower_bound,upper_bound使うらしい。

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
const int INF = 1e9;

typedef pair<int, int> P;
const int MAX_N = 1000005;
P dp[MAX_N];
multimap<int, int> mp;

signed main()
{
    int n;

    cin >> n;
    vector<int> a(n), b(n);
    int mx = 0; //終了時刻の最大値
    REP(i,n) {
        cin >> a[i] >> b[i];
        //multimapに要素を追加
        //開始時刻と仕事の番号
        mp.emplace(a[i], i);    
        mx = max(b[i], mx);
    }

    //P(取れる仕事の最大数, 仕事番号の最小値)
    dp[mx] = P(0, INF);
    for (int i=mx-1; i>=0; i--) {
        P p = dp[i+1];
        //開始時刻がiのものを全て見る
        for (auto it=mp.lower_bound(i); it!=mp.upper_bound(i); it++) {
            int id = it->second;
            if (dp[b[id]].first + 1 > p.first) {
                p.first = dp[b[id]].first + 1;
                p.second = id + 1;
            } else if (dp[b[id]].first + 1 == p.first) {
                p.second = min(p.second, id + 1);
            }
        }
        dp[i] = p;
    }

    int cnt = dp[0].first;
    cout << cnt << endl;
    int nw = 0;
    REP(i,cnt-1) {
        P p = dp[nw];
        cout << p.second << " ";
        nw = b[p.second-1];
    }
    P p = dp[nw];
    cout << p.second << endl;
}