AtCoder Regular Contest 030 C - 有向グラフ

競技プログラミング

問題

　n頂点m辺の有向グラフが与えられる。各頂点にはアルファベットが一つ書かれている。

　このグラフを好きな頂点から任意の順番で訪問し、k個のアルファベットを回収することを考える。頂点は何度も訪問することができ、ある頂点に書かれたアルファベットは任意の訪問タイミングで回収できる。このとき回収してできる文字列として辞書順最小のものを求めよ。

解法

　強連結成分分解をしてできたグラフについてDPを行う。

反省

　3時間8分(8WA)でAC。最初は普通にDPやるだけかと勘違いして実装したが、一度取ったらなくなるのでどこ頂点から取ってあるのかを状態として持たないといけないことに提出してWA出てから気づく。そこからしばらく考えたが計1時間ほど考えてわからなかったので解説スライドを見た。

　解法を知ってからの実装が大変な問題だった。まず強連結成分分解のアルゴリズムがスライドだけではよくわからなかったので他のページなど見ながらなんとか実装していく。さらにその後のDPも結構複雑で、他人の提出を見ないとわからなかった。

　強連結成分分解を2回の深さ優先探索で実装すれば、その後のグラフを再度トポロジカルソードし直す必要はないのだろうか。自分の提出では特にそういうことをしていないので、それで通ったということはすでにトポロジカル順に並んでいる気がする(し、アルゴリズム的にもなんとなくそういう感じなんじゃないかと思われるが……)。

　ライブラリにしやすい感じで書いたので、強連結成分分解が必要な問題に当たったらこの回の自分の提出を再利用したい。以前見たことがあるのはAlien's Countingで、これも強連結成分分解してからDPという感じだったと記憶しているので、ある種の典型ではあるのだろうか。

　最終的な実装がいろいろ終わってからもループの範囲をミスってREを出しまくってしまった。難しい実装と些細なミスが絡むと原因が分からなくなって大変なことになってしまう。気を付けていきたい。

コード

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

class StronglyConnectedComponents {
public:
    StronglyConnectedComponents(ll n) :
        n_(n),
        edges_(n),
        reverse_edges_(n),
        order_(n),
        num_(0) {}
    
    void addEdge(ll from, ll to) {
        edges_[from].push_back(to);
        reverse_edges_[to].push_back(from);
    }

    vector<vector<ll>> scc() {
        visit.assign(n_, false);
        for (ll i = 0; i < n_; i++) {
            dfsForward(i);
        }
        sort(order_.begin(), order_.end(), [](const Order& lhs, const Order& rhs) {
            return lhs.order > rhs.order;
        });
        visit.assign(n_, false);
        for (ll i = 0; i < n_; i++) {
            auto curr_result = dfsBackward(order_[i].index);
            if (curr_result.size() == 0) {
                continue;
            }
            result_.push_back(curr_result);
        }
        return result_;
    }

    vector<vector<ll>> sccEdges() {
        vector<vector<ll>> scc_edges(result_.size());
        vector<ll> indexToScc(n_);
        for (ll i = 0; i < (ll)result_.size(); i++) {
            for (ll j : result_[i]) {
                indexToScc[j] = i;
            }
        }

        for (ll i = 0; i < (ll)result_.size(); i++) {
            for (ll from : result_[i]) {
                for (ll to : edges_[from]) {
                    if (indexToScc[to] == i) {
                        continue;
                    }
                    scc_edges[i].push_back(indexToScc[to]);
                }
            }
        }
        return scc_edges;
    }
private:
    void dfsForward(ll curr) {
        if (visit[curr]) {
            return;
        }
        visit[curr] = true;
        for (ll next : edges_[curr]) {
            dfsForward(next);
        }
        order_[curr] = { curr, num_++ };
        return;
    }

    vector<ll> dfsBackward(ll curr) {
        vector<ll> curr_result;
        if (visit[curr]) {
            return curr_result;
        }
        visit[curr] = true;
        curr_result.push_back(curr);
        for (ll next : reverse_edges_[curr]) {
            auto members = dfsBackward(next);
            for (ll m : members) {
                curr_result.push_back(m);
            }
        }
        return curr_result;
    }

    ll n_;
    vector<vector<ll>> edges_;
    vector<vector<ll>> reverse_edges_;
    struct Order {
        ll index, order;
    };
    vector<Order> order_;
    vector<bool> visit;
    vector<vector<ll>> result_;
    ll num_;
};

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<char> c(n);
    for (ll i = 0; i < n; i++) {
        cin >> c[i];
    }

    StronglyConnectedComponents scc(n);
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        scc.addEdge(a, b);
    }

    auto scc_result = scc.scc();
    auto scc_edges = scc.sccEdges();

    ll N = scc_result.size();
    vector<string> scc_chars(N);
    for (ll i = 0; i < N; i++) {
        for (ll j : scc_result[i]) {
            scc_chars[i].push_back(c[j]);
        }
        //ソートしておく
        sort(scc_chars[i].begin(), scc_chars[i].end());
    }

    vector<vector<string>> dp(N + 1, vector<string>(k + 1));

    for (ll i = N - 1; i >= 0; i--) {
        for (ll j = 0; j <= min((ll)scc_result[i].size(), k); j++) {
            string str = scc_chars[i].substr(0, j);
            if (dp[i][j].empty() || dp[i][j] > str) {
                dp[i][j] = str;
            }
            for (ll next : scc_edges[i]) {
                for (ll l = 1; l <= k - j; l++) {
                    if (l > 0 && dp[next][l].empty()) {
                        break;
                    }
                    string tmp = str + dp[next][l];
                    if (dp[i][j + l].empty() || dp[i][j + l] > tmp) {
                        dp[i][j + l] = tmp;
                    }
                }
            }
        }
    }

    string ans;
    for (ll i = 0; i < N; i++) {
        if (dp[i][k].empty()) {
            continue;
        }
        if (ans.empty() || ans > dp[i][k]) {
            ans = dp[i][k];
        }
    }

    cout << (ans.empty() ? "-1" : ans) << endl;
}