Atcoder beginner contest 222 E問題の深さ全探索で求めた最短経路の復元が正しくできない

Question

前提・実現したいこと

ABC222のE問題を以下のコードで解いたのですが、すべてACになりません。また、自分の実行環境とAtcoderのコードテストで動かした結果が同じサンプル入力を使っているにもかかわらず、一致しません。汚いコードで申し訳ないのですが、原因を教えていただけると幸いです。

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int INF = 1e9;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <typename Type> inline string toString(const Type &a){ostringstream oss; oss << a; return oss.str();}

int N, M, K;
const int mod = 998244353;
vector<int> A, C, prev_v;
vector<vector<pair<int, int>>> G;
vector<vector<ll>> dp;

// first... target, second... edge id
void dfs(int v, int goal){
    if(v == goal) return;
    for(pair<int, int> nv : G[v]){
        if(prev_v[nv.first] == -1 || prev_v[nv.first] != INF || nv.first == prev_v[v]) continue;
        prev_v[nv.first] = v;
        dfs(nv.first, goal);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K;
    A.resize(M);
    G.resize(N);
    for(int i = 0; i < M; ++i){
        cin >> A[i];
        A[i]--; 
    }
    for(int i = 0; i < N - 1; ++i){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(make_pair(b, i)); G[b].push_back(make_pair(a, i));
    }


    C.assign(N - 1, 0);
    for(int i = 0; i < M - 1; ++i){
        prev_v.assign(N, INF);
        prev_v[A[i]] = -1;
        dfs(A[i], A[i + 1]);
        int cur = A[i + 1];
        while(cur != A[i]){
            int edge_id = G[cur][prev_v[cur]].second;
            cout <<  "cur = " << cur << " edge id = " << edge_id << '\n';
            C[edge_id]++;
            cur = prev_v[cur];

        }
    }
    ll sumC = 0;
    for(int i = 0; i < N - 1; ++i) sumC += C[i];
    if((K + sumC) % 2 == 1 || K + sumC < 0){
        cout << 0 << endl;
        return 0;
    } 
    dp.assign(N, vector<ll>((K + sumC) / 2 + 1 , 0));
    dp[0][0] = 1;
    for(int i = 0; i < N - 1; ++i){
        for(int j = 0; j <= (K + sumC) / 2; ++j){
            if(C[i] <= j){
                dp[i + 1][j] += dp[i][j - C[i]];
                dp[i + 1][j] %= mod;
            }
            dp[i + 1][j] += dp[i][j];
            dp[i + 1][j] %= mod;
        }
    }

    cout << dp[N - 1][(K + sumC) / 2] << endl;
}

試したこと

• 入力サンプル１を試した結果、自分の環境では2になるが、atcoderのコードテストでは0になる
• 配列prevには正しい答えが入力されている(以下入力サンプル3を試した場合)

　prev_v = -1 0 1 2 3 4 5 6 7 8
しかしedge_idの値に誤りがあると思われる。実行結果はこのようになったが、
cur = 9 edge id = 3
cur = 8 edge id = 0
cur = 7 edge id = 0
cur = 6 edge id = 8
cur = 5 edge id = 6
cur = 4 edge id = 5
cur = 3 edge id = 3
cur = 2 edge id = 2
cur = 1 edge id = 0
このサンプルケースではどの辺も一回ずつしか通らないはず。これによって、このあとのdpで使う配列Cを正しく作ることができない。

補足情報（FW/ツールのバージョンなど）

使用しているコンパイラ...gcc12.0.5

Comments

[actorbug]

まじめに追ってませんが、vectorの範囲外アクセスがあるようです。
サンプル1を入力すると、以下の箇所(52行目)で範囲外アクセスが見つかります。
int edge_id = G[cur][prev_v[cur]].second;

[rdld036]

グラフGの各要素はpair型で、
37行目の
　for(int i = 0; i < N - 1; ++i){
int a, b;
cin >> a >> b;
a--; b--;
G[a].push_back(make_pair(b, i)); G[b].push_back(make_pair(a, i));
}
よりsecondにはエッジのidが入っているのではないでしょうか？

[actorbug]

「secondにはエッジのidが入っている」は正しいですが、それが正しかったからと言って、今回の指摘(vectorの範囲外アクセスがある)が誤りであるということにはなりません。
範囲外アクセスがあるのは、C[edge_id]++;ではなく、int edge_id = G[cur][prev_v[cur]].second; になります。

具体的な動作内容を回答に追記したので、そちらで確認をお願いします。

gccを使っているなら、ソースの先頭に「#define _GLIBCXX_DEBUG」を追加してビルド・実行することで、範囲外アクセスを検出することができるそうです。

Answer 1

問題は以下の箇所です。

int edge_id = G[cur][prev_v[cur]].second;

prev_v[cur]は、curの前の頂点のインデックスになります。
そして、G[cur]は、curにつながる辺のvectorになります。
辺のvectorについて、頂点のインデックス番目の要素を取得しているのが誤りです。

---

具体的に、サンプル1で何が起こっているかを順に追っていきましょう。

まず、入力の読み込みで、A,Gはそれぞれ以下のようになります。
({}はvector、()はpairのつもりです)

A = { 1, 2, 1, 0, 3 };
G = { { (1,0) }, { (0,0), (2,1) }, { (1,1), (3,2) }, { (2,2) } };

読み込んだ後のforループで、i = 1 の場合の処理を追ってみましょう。

まず、

prev_v.assign(N, INF);
prev_v[A[i]] = -1;
dfs(A[i], A[i + 1]);

により、prev_vは以下のようになります。

prev_v = { INF, 2, -1, 2 };

次に、

int cur = A[i + 1];

により、cur = 1 となります。

その次のwhileの条件は当然満たすとして、問題の以下の処理について考えます。

int edge_id = G[cur][prev_v[cur]].second;

G[cur] = { (0,0), (2,1) }、prev_v[cur] = 2 なので、
G[cur][prev_v[cur]] は、{ (0,0), (2,1) } の2番目の要素を取得しようとします。
しかし、要素が2つしかないので範囲外アクセスとなります。

Comments

[rdld036]

返信が遅くなって申し訳ありません。
このように前の頂点に通じる辺を取り出していけば良いということでしょうか。　
pair<int, int> edge;
for(pair<int, int> e : G[cur]){
if(e.first == prev_v[cur]){
edge = e;
}
}

C[edge.second]++;
cur = prev_v[cur];

[actorbug]

そういうことです。

[rdld036]

レビューだけでなく、デバッグの方法についても丁寧にアドバイスしていただき誠にありがとうございます。