AtCoder ABC291 F - Teleporter and Closed off

F - Teleporter and Closed off

考えたこと

・幅優先探索やダイクストラ法では間に合わなそう

最短経路探索といえば幅優先探索やダイクストラ法だが、この問題では使っても間に合わなそうに見える。
これらのアルゴリズムは頂点や辺の変化に弱く、「特定の頂点が通れなくなったら」「特定の辺が通れなくなったら」などの変化を1つ与えただけで既存の経路探索結果は使えなくなってしまう。
探索し直す回数が100回程度なら間に合うが、今回は最大で約10^5回である。間に合うはずがない。

Mが最大10なので、一度探索した経路について通れなくなった都市の前後M点だけ再探索できないかとも考えてみたが、以下のようなケースに対応できない。
　・N = 41
　・M = 10
　・経路1：1→11→21→31→41
　・経路2：1→2→3→4→5→6→7→8→9→10→12→(以下略)
　　　※11, 21, 31以外の全てを通るようにする
　・この2つの経路しかない
この場合、都市21番を通れなくすると最短経路は経路2になるが、都市1番の段階で違う経路を通ることになるので、最短経路を部分的に再探索するのでは導出できない。

・特定の点を通るようにした最短経路は簡単に求めることができる

例えば1番から5番を通り10番へ向かう最短経路を求めたい場合には、
　・1番から5番までの最短経路
　・5番から10番までの最短経路
の和を取ることで求めることができる。
同様に、途中で2つの点(a, b)を通るようにしたければ
　・1番から中継地点aまでの最短経路
　・中継地点aから中継地点bまでの最短経路
　・中継地点bから10番までの最短経路
の和を取ればいい。

・1番→中継a→(都市kを飛ばして直接)→中継b→N番とすればいい

都市kを通らないようにした最短経路を求めるならば、上記の「途中で2つの点(a, b)を通るときの最短経路」を求める方法が使える。
例えば
　・N = 10
　・M = 3
　・k = 5
のとき、5番を通らないようにすればいいので、その選択肢は
　　1番→(最短で)→3番→(1手で)→6番→(最短で)→10番
　　1番→(最短で)→4番→(1手で)→6番→(最短で)→10番
　　1番→(最短で)→4番→(1手で)→7番→(最短で)→10番
の3つしかない。この3経路の最短距離が答えとなる。
選択肢の総数はM * (M-1) / 2となるが、Mが最大10なので最大の選択肢の総数は45個である。2≦k≦N-1の全てのkに対してこの最大45個を総当たりするのは可能である。

よってこの問題は
　① 1番から全ての点への最短経路を求める
　② 全ての点からN番への最短経路を求める
　③ 通らないkを1点決め、kを通らない経路(最大45通り)を総当たり
　④ ③を2～N-1でループ
で解くことができる。①と②は幅優先探索でもダイクストラ法でもDPでも求めることができるのでお好みの方法で求めればいい。
②を求める場合は、始点をNにしてすべての辺を逆向きに貼りなおせば①と同様の方法で求めることができる。

書いたコードと提出結果

#include <bits/stdc++.h>

int main(){
    int N, M;
    std::cin >> N >> M;
    std::vector< std::string > S(N);
    for(int i=0; i<N; i++){
        std::cin >> S[i];
    }
    
    std::vector< int > dists(N, 1e9);
    dists[0] = 0;
    for(int i=1; i<N; i++){
        for(int j=0; j<M; j++){
            if(i-j-1 == -1){
                break;
            }
            if(S[i-j-1][j] == '1'){
                dists[i] = std::min(dists[i], dists[i-j-1] + 1);
            }
        }
    }
    
    std::vector< int > distt(N, 1e9);
    distt[N-1] = 0;
    for(int i=N-2; i>=0; i--){
        for(int j=0; j<M; j++){
            if(i+j+1 == N){
                break;
            }
            if(S[i][j] == '1'){
                distt[i] = std::min(distt[i], distt[i+j+1] + 1);
            }
        }
    }
    
    for(int i=1; i<N-1; i++){
        int min = 1e9;
        for(int a=i-M+1; a<=i-1; a++){
            if(a < 0 || dists[a] == 1e9){
                continue;
            }
            for(int b=i+1; a+M>=b; b++){
                if(b >= N || distt[b] == 1e9){
                    continue;
                }
                if(S[a][b-a-1] == '1'){
                    min = std::min(min, dists[a] + distt[b] + 1);
                }
            }
        }
        if(min == 1e9){
            std::cout << -1 << std::endl;
        }else{
            std::cout << min << std::endl;
        }
    }
    
    
    return 0;
}

Submission #39284016 - AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）