密なグラフの最短経路探索

Fastestメモ

もう競技プログラミングは引退気味かなと思いつつ、それならFastest Submissionをそれなりに頑張った私の工夫とか公開していけば誰かの役に立つんじゃないのと思って、記事を書くようにしようと思いました。

ABC218のFで、頂点400の密なグラフで高速にBFSができた気がするので、この記事にメモ程度に残します。
Submission #27464352 - AtCoder Beginner Contest 218

まず密なので、隣接行列で辺を管理します。
単純な隣接行列では400*400のテーブルで辺の有無を管理しますが、今回はlong longの64ビット単位で計算して高速化を目指します。
そこで以下のような感じで頂点uから頂点vへの辺をまとめました。

long long E[400][7] = {}, vis[7] = {};
for (int i = 0; i < M; i++) {
	int u, v;
	cin >> u >> v;
	E[u][v >> 6] |= 1ll << (v & 63);
}

7は400 / 64の切り上げです。
さらに、頂点にすでに訪れたかどうかも”long long vis[7]”のビットごとに割り当てて管理することにします。ただ、ここまでだと省メモリくらいの効果しかありません。

ある頂点uから辺をたどるとき、隣接行列だと単純な方法では行先のN(=400)頂点への辺があるか一つずつチェックすることになりますが、ここを高速化します。

for (int i = 0; i < 7; i++) {
	long long t = (E[u][i] | vis[i]) ^ vis[i];
	vis[i] |= t;
	while (t) {
		Queue.push(i << 6 | __builtin_ctzll(t));
		t -= t & -t;
	}
}

BFSを想定して行先をQueueにpushするように書いています。
ポイントはいくつかあります。

"long long t"は「辺E[u][i]にはあるが、vis[i]にはない」つまり未訪問の頂点のビットが立っている状態になっています。
"while(t)"は「未訪問の頂点が残っているかぎり」となります。
"i << 6 | __builtin_ctzll(t)"は、tの立っているビットのうち最下位のものを頂点番号に戻したものです。
"t -= t & -t"は立っている最下位ビットだけを0にする魔法です。Binary Indexed Tree (Fenwick Tree)で見かけた方もいると思います。

これで綺麗に未訪問の頂点へ向かう全ての辺をたどれます。

肝心の速度はどうなっているかというと、
多くの頂点が訪問済みの場合、7(N / 64)回のループとt=0の確認だけになるので、単純な方法でN回ループするより高速です。
多くの頂点が未訪問の場合、未訪問を見つける度に演算を挟むので当然その瞬間は遅いですが、この未訪問への訪問は全体を通して高々N回しか起こりません。ゆえにこの処理は全体の計算量を悪化させません。

これでいい具合に現時点のFastestはとれました。