Google Code Jam 2014 Round 1B : C. The Bored Traveling Salesman

問題設定がややこしい…。
https://code.google.com/codejam/contest/2994486/dashboard#s=p2

問題

N個の都市があり、互いにM種類の航空便がある。
これらの都市を順に全部たどり、それぞれ初めて到着した際に現地の郵便番号を連結させて文字列を生成したとき、辞書順最小の文字列を作りたい。

この際、移動のルールは以下の通りである。

• 開始する都市はどこでも良い。
• 航空便のチケットは行きと帰りの2枚組であり、そのチケットを使う場合は行き→帰りの順で使い切らないといけない。
• ある都市に行く際、行きのチケットで行けるのは1回だけである。帰りのチケットで到達するのは何回でも良い。

解法

チケット云々の下りがわかりにくいが、問題文を言い換えるとこうなる。
「任意の都市から深さ優先探索順で全都市をたどって戻る際、経由した都市の郵便番号の連結文字列を最小化せよ」

辞書順最小を目指すので、当然開始都市は最小の郵便番号の都市である。
以下以下のルールで各都市をDFSで回る。その際、そこまでの経路をスタックで管理しておく。

• 未到達の都市を郵便番号が小さい順に探し、未到達都市があった場合：
  • 今の都市から移動可能ならそこに移動してDFSする。DFSから戻ってきたら、未到達都市探索を最初からやり直す。
  • 今の都市から移動不可能なら、今の都市から戻って以前の都市からDFSを継続した方がいいか確認する。この手順は以下の通り。
    • スタックにある都市を順にチェックし、それらの都市から未到達の都市に全部到達可能か検証する。全部到達可能でかつ探した未到達都市に到達できる都市がスタック中にあるなら、今の都市のDFSをやめる。

ややこしいけど、簡単に書くと
「基本的には辞書順最小の都市を貪欲にたどる。今見ている都市から辞書順最小の未到達都市に到達できそうにない場合、今ここでDFSを中断しても、スタック中の都市から未到達都市に全部たどれるなら中断する。そうではなく、今いる都市から行けない未到達都市があるなら先にそちらをたどる」
となる。

以下のコードはO(N^4)位かな？

int N,M;
int Z[101];
ll mat[101];
vector<int> R,st;

ll reach(int cur, ll mask) {
	int i;
	queue<int> Q;
	Q.push(cur);
	while(!Q.empty()) {
		cur=Q.front();
		Q.pop();
		FOR(i,N) if((mat[cur]&(1LL<<i)) && ((mask&(1LL<<i))==0)) {
			mask |= 1LL<<i;
			Q.push(i);
		}
	}
	return mask;
}

ll dfs(int cur, ll mask) {
	int i;
	R.push_back(cur);
	mask |= 1LL<<cur;
	
	st.push_back(cur);
	
	int tar;
	retry:
	FOR(tar,N) if((mask & (1LL<<tar))==0) {
		if(mat[cur]&(1LL<<tar)) {
			mask=dfs(tar,mask);
			goto retry;
		}
		ll nm=mask;
		FOR(i,st.size()-1) {
			nm |= reach(st[i],mask);
			if((nm+1==(1LL<<N)) && (mat[st[i]]&(1LL<<tar))) goto out;
		}
	}
	out:
	st.pop_back();
	return mask;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y,z;
	
	map<int,int> C;
	cin>>N>>M;
	FOR(i,N) {
		cin>>Z[i];
		C[Z[i]]=i;
	}
	i=0;
	int conv[51];
	ITR(it,C) Z[i]=it->first, conv[it->second]=i++;
	
	
	ZERO(mat);
	FOR(i,M) {
		cin>>x>>y;
		x=conv[x-1];
		y=conv[y-1];
		mat[x] |= 1LL<<y;
		mat[y] |= 1LL<<x;
	}
	
	R.clear();
	st.clear();
	dfs(0,0);
	
	_P("Case #%d: ",_loop);
	FOR(i,N) _P("%d",Z[R[i]]);
	_P("\n");
}

まとめ

結構ややこしいけどスタックを使うとは面白いデータ構造の問題だった。