AtCoderのXOR最小値問題の解法とデバッグポイント

AtCoderの競技プログラミング問題でよく見かけるグラフ関連の問題には、探索アルゴリズムやXOR演算を駆使するものが多いです。この記事では、頂点と辺の情報を元に、最小のXOR値を求める問題における誤りを特定し、解法のポイントと共にその修正方法について詳しく解説します。

問題の概要と誤解しやすい部分

問題の設定は、単純連結無向グラフの頂点1から頂点Nまでのパスに含まれる辺のラベルのXORの最小値を求めるものです。このXORを最小化することが求められます。

最初に投稿されたコードでは、深さ優先探索（DFS）を用いて解こうとしていますが、いくつかの問題点があります。特に、訪問済みの頂点を戻す処理やXORの計算に関連する部分に問題があります。

DFS探索アルゴリズムの基本的な流れ

深さ優先探索（DFS）を用いる場合、まず探索を開始する頂点からスタートし、再帰的に隣接頂点を探索していきます。再帰的に呼ばれる際、XORの値を引き継いで、最小値を更新していくことが基本です。

コードでは、`dfs`関数が実装されていますが、探索途中で訪れた頂点を戻す処理（`visited[pos] = false`）が不適切に行われています。これにより、探索の重複や誤った結果が生じる可能性があります。

問題点の指摘と修正方法

具体的な問題点は、以下の2点です。

• 1. 訪問済みフラグの戻し方
  DFSの探索後に頂点を訪問済み状態に戻す際、`visited[pos] = false`を`dfs`関数の終了後に行っていますが、この位置だと正しく動作しない場合があります。正しくは、再帰呼び出しが終了した後、親の探索に戻る直前にフラグを戻す必要があります。
• 2. XORの計算順序
  XOR演算を行うタイミングが誤っています。`x^g[pos][i].second`の演算は探索前に行い、再帰に渡す際にその値を引き継ぐようにしましょう。

修正後のコード例

以下のコードは、上記の問題を修正したバージョンです。

#include
#include
using namespace std;
vector>> g(11);
long long ans=2e18;
bool visited[11];
int n,m;
//dfs探索
void dfs(int pos,long long x){
  visited[pos]=true;
  if(pos==n){
    ans=min(ans,x);
    return;
  }
  for(int i=0;i<(int)g[pos].size();i++){ 
    int nex=g[pos][i].first;
    if(!visited[nex]){
      dfs(nex,x^g[pos][i].second);
    }
  }
  visited[pos]=false;
}
int main(){
  cin>>n>>m;
  for(int i=0;i>a>>b>>w;
    g[a].push_back(make_pair(b,w));
    g[b].push_back(make_pair(a,w));
  }
  for(int i=1;i<=n;i++) visited[i]=false;
  dfs(1,0);
  cout<