One Step at a Time [第六回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202104-open/tasks/past202104_g

解説

https://atcoder.jp/contests/past202104-open/submissions/22652811

何から始めようかという感じであるが、愚直なやり方から考えてみる。

愚直に探索できないか

操作を行っていく上で訪れることができるかどうかを管理しながら探索してみたくなる。
なので、訪れることができる頂点について配列で管理しておこう。

vis[cu] := 都市cuを訪れることができるか

これを更新していくことを考えると、すべての日について、
vis[cu]=trueである都市からX[i]以下の道で移動可能な都市に移動可能なことが言える。
よって、全ての日についてvis[cu]=trueである全ての都市を確認して、そこからX[i]以下の道で移動可能な都市toについてvis[to]=trueとする操作をする。
この操作後にtrueである個数を数えれば答えが導ける。

これをそのまま実装すると、日数がQで、都市数がNで、辺数がMなので、O(Q(N+M))となる。
全ての都市について確認して、かつ、遷移を全部確認すると、遷移で用いられる辺数はならしで2M回の評価になるので、NとMの大きい方が計算量を支配する。
よってN+Mみたいな表記になる。

これは10¹⁰を超えてしまうので間に合わない。この処理を最適化できないだろうか。

不必要な処理

毎日すべての都市と辺を確認していると、もう必要ないのに確認している部分が多く発生する。
都市視点で見ると後々の日付で小さいXが出てきたら、そこから遷移が発生する場合があるので、最適化難しそう。
だが、「辺については1度使用されたら、それを再度使用しても移動できる都市は増えない」ことが言える。
なので、辺はダブって確認する必要はないことを利用して最適化できないかということが考えられる。

都市始点というのが少し面倒だが、よくよく考えれば確認すべきなのは全ての辺であって、vis[cu]=trueであるすべての都市を確認する必要はなく、
全ての辺(cu,to)についてvis[cu]=trueまたはvis[to]=trueである辺で遷移を行ってやればそれでいい。

良い感じに条件をそぎ落とすことができた。
Q日間あるが、それを通して辺の評価をそれぞれ1回に限定することができればならしで計算量をO(Q+M)に抑えることができる。
これは間に合う計算量だ。

辺を管理する

辺を管理することにしよう。
以下のようなものを用意しよう。

que := 辺の少なくとも片方はいる可能性があって（vis[]=true）、かつ、まだ遷移で使用されていない辺の集合

毎日、ここから使える辺を効率良く持ってくることができれば、うまく実装まで持ち込める。
使える辺とは具体的にはX[i]以下のコストを持つ辺ということになるが、priority_queueを使えばそれが実現できる。
queをpriority_queueとして（C++のデフォルトでは降順ソートなので注意）、入れるときに(コスト, 遷移先の都市)としておけば、先頭が最もコストが小さく使える辺となる。
なので、先頭から順番に見ていってコストがX[i]以下のものをすべて取り出してきて評価すれば、要求が満たせる。

あとは、遷移可能な頂点が増えたときにそこからの辺をqueに追加していけば良し。

int N, M, Q;
vector<pair<int, int>> E[201010];
//---------------------------------------------------------------------------------------------------
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
min_priority_queue<pair<int, int>> que;
bool vis[201010];
int ans = 0;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;
    rep(i, 0, M) {
        int A, B, C;
        cin >> A >> B >> C;
        A--; B--;

        E[A].push_back({ B, C });
        E[B].push_back({ A, C });
    }

    vis[0] = true;
    ans++;
    fore(p, E[0]) que.push({ p.second, p.first });;

    rep(_, 0, Q) {
        int X; cin >> X;

        vector<pair<int, int>> nxt;
        while (!que.empty() && que.top().first <= X) {
            auto q = que.top();
            que.pop();

            if (vis[q.second]) continue;

            vis[q.second] = true;
            ans++;
            fore(p, E[q.second]) nxt.push_back({ p.second, p.first });;
        }
        fore(p, nxt) que.push(p);

        printf("%d\n", ans);
    }
}