はまやんはまやんはまやん

hamayanhamayan's blog

Greedy Takahashi [AtCoder Beginner Contest 212 F]

https://atcoder.jp/contests/abc212/tasks/abc212_f

前提知識

解説

https://atcoder.jp/contests/abc212/submissions/24698572

最終的にはダブリングを使用して解く。
ダブリングについては説明しないので、どこかで学習してきてほしい。

重要性質

グラフの問題を考えるときは頂点を状態として考えたくなるが、とある頂点からの遷移を考えると、
この頂点にいる時間によって遷移先が変わってしまう。
なので、状態を考える場合に(頂点, 時間)というセットで考えなくてはならなくなる。
だが、この時、状態として考えるべき時間は、遷移に必要な両端の時間に限られる。
これは実質的に考えると辺の両端が状態として考えられていることになる。
これなら状態数はO(M)となるので、まだ管理できることになる。
なので、状態は辺を中心に考えた方がよさそうである。

そのうえで出てくる大切な性質が、とある辺が使われた後に使用される辺は一意に定まるということである。
これはよく見ると、問題文にも「M本のバスの出発時刻は互いに異なることが保証されるため、
高橋くんが乗るバスは常に一意に定まります。」とやや触れられていることである。

解答方針「シミュレーション高速化」

この性質を元に解法方針を考えてみる。
今回の方針は「シミュレーション高速化」である。
Q個のクエリがあるが、各クエリについて高速にシミュレーション、つまり、
バスの移動を行って最終的な状態を答えることにする。

バスの移動で1回や2回、場合によっては10000回行うことになると思うが、これを高速化する。
移動を高速化といえば、そして、条件として移動先が一意に定まるといえば、ダブリングである。

ダブリング

dp[edge][p] := 辺edgeを最後に使った状態で、2p回辺を使って移動したときに最後に使った辺の番号

このように定義すると、dp[edge][p] = dp[ dp[edge][p-1] ][p-1]と更新することでテーブルが作れる。

初期状態を作るのがやや厄介かもしれない。

dp[edge][0] := 辺edgeを最後に使った状態で、1回辺を使って移動したときに最後に使った辺の番号

これは辺edgeを最後に使ったということなので、状態としては、頂点B[edge]にT[edge]時間でいるということになる。
なので、B[edge]が始発でT[edge]時間に最も近い辺を持ってくればいい。
これは自分の実装ではgetNextIndex関数として実装している。

getNextIndex(int position, int curtime) := position頂点にcurtime時間でいるときに次使われる辺の番号(もしなければMを返す)

遷移できないときはMを返すようにしておいて、dp[M][p] = Mとしておけばいい感じにループしてくれて場合分けがいらなくなる。

シミュレーション高速化

あとは、ダブリングテーブルを使って時間を確認していく。
219回移動した場合、218回移動した場合というのを順に試していけばいい。
移動するかどうかは、移動後に見たい時間を過ぎてしまっているかを判定する。
過ぎてしまっているなら、その回数移動はできないし、過ぎていないなら、その回数移動できるので移動する。
最終的に、最後の一手の手前までくるはずなので、辺と時間の関係性を見ながら、移動前か、移動中か、移動後かを判定して答えを出す。

int N, M, Q;
int A[101010], B[101010], S[101010], T[101010];
vector<pair<int, int>> E[101010];
int dp[101010][20];
//---------------------------------------------------------------------------------------------------
int getNextIndex(int position, int curtime) {
    auto res = lower_bound(all(E[position]), make_pair(curtime, -1));
    if (res == E[position].end()) return M;
    return res->second;
}
//---------------------------------------------------------------------------------------------------
pair<int,int> getAns(int X, int Y, int Z) {
    int nearest = getNextIndex(Y, X);
    if (nearest == M) return { Y, -1 };
    if (Z <= S[nearest]) return { Y, -1 };
    else if (S[nearest] < Z && Z <= T[nearest]) return { A[nearest], B[nearest] };

    int curtime = T[nearest];
    int curedge = nearest;
    
    rrep(p, 19, 0) {
        int nxt = dp[curedge][p];
        if (nxt == M) continue;
        if (T[nxt] < Z) {
            curtime = T[nxt];
            curedge = nxt;
        }
    }

    nearest = getNextIndex(B[curedge], curtime);
    if (nearest == M) return { B[curedge], -1 };

    if (Z <= S[nearest]) return { A[nearest], -1 };
    if (S[nearest] < Z && Z <= T[nearest]) return { A[nearest], B[nearest] };
    return { B[nearest], -1 };
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;
    rep(i, 0, M) {
        cin >> A[i] >> B[i] >> S[i] >> T[i];
        A[i]--, B[i]--;
        E[A[i]].push_back({ S[i], i });
    }
    rep(i, 0, N) sort(all(E[i]));

    rep(edge, 0, M) dp[edge][0] = getNextIndex(B[edge], T[edge]);
    rep(p, 0, 20) dp[M][p] = M;
    rep(p, 1, 20) rep(edge, 0, M) dp[edge][p] = dp[dp[edge][p - 1]][p - 1];

    rep(_, 0, Q) {
        int X, Y, Z; cin >> X >> Y >> Z; Y--;
        auto ans = getAns(X, Y, Z);
        printf("%d", ans.first + 1);
        if (0 <= ans.second) printf(" %d", ans.second + 1);
        printf("\n");
    }
}