cafelier@SRM

ICPC 2019 Japan Domestic 問題F

その他 | 23:31 |

ICPC 2019 国内予選 の問題F (AOJ:1637) について考えてみたよ、というか、色んな人の色んな解法を聞いて面白かったので自分なりにまとめてみました。

こういう問題です。『無向グラフが与えられます。頂点を押すと、その頂点と他の全ての頂点の接続関係が反転します。辺で繋がってたところは辺が消え、繋がってなかったところには辺が生えます。この操作を繰り返して全域木が作れますか。作れるならコスト最小のものを。』

脱線

ところで、こういう頂点の周りの辺を反転する操作は Seidel のスイッチング と呼ばれていて、元々は楕円幾何学という数学の問題を解くための道具として研究され始めたようです。

• J. H. van Lint and J. J. Seidel, "Equilateral Point Sets in Elliptic Geometry"

Equilateral Point Set というのは多分どの2点間の距離も等しいような点集合ということで、2次元ユークリッド平面上だったら正三角形の頂点3点がEquilateralだし、3次元ユークリッド空間なら正四面体で4点かな？楕円幾何学という曲がった空間だともっと大きな点集合がEquilateralになり得るのですが、さて実際のところ、r次元の空間で最大何点がEquilateralになるのだろうか、求めたい、というお話だったそうです。

なぜグラフが出てくるかというと、この幾何の問題は行列にエンコードすることができて、n*n行列に対してある操作を繰り返した結果の行列の固有値がある条件を満たせばEquilateral、みたいになるのですが、その行列をグラフの隣接行列として解釈すると、行列操作がグラフのSeidelのスイッチングに対応するのだとか（よくわかってないのであやふやなコメントです。）

というわけでこの論文では、7次元のEquilateral setを求めるために、7頂点グラフを反転させまくって作れる同値類を列挙して(page 339-340)楽しんでいました。楽しそうですね。

Seidel Switching で検索してみると、最近は スペクトラルグラフ理論 やグラフスペクトル理論と呼ばれる系のお話でよく参照されているようです。グラフを隣接行列という行列の形で表現してみたり、最近バズっていた記事で行列冪乗と最短路計算を結びつけたりみたいな話がありますけど、せっかく行列という線形代数っぽいものを持ち出すのだからもっと線形代数っぽい話をしようというのがスペクトラルグラフ理論で、具体的には、隣接行列などのグラフから作れる行列の固有値からグラフの性質を探る理論です。行列の掛け算くらいならまだしも、固有値なんてグラフ的に何か意味がある値になるんでしょうか。気になった方は、ir5さんによる「スペクトラルグラフ理論入門」というスライドなどお勧めです。

Seidel switching は、「特定の形のグラフに適用すると、固有値は変わらないが元のグラフと同型ではないグラフを作る」という道具としてよく言及されています。固有値が完全にグラフの形を語り切っているわけではなく抽象していることの証明として使われているわけですね。

以上の話はアルゴリズムと言うよりはグラフ理論寄りの話でしたが、

• A. Ehrenfeucht, J. Hage, T. Harju, and G. Rozenberg, "Complexity Issues in Switching of Graphs"

という研究などは、スイッチングで到達できる範囲内に条件を満たすグラフがあるかの判定問題の解き方や計算複雑性の考察をしています。目標のグラフに次数が低いノードが必ずあるならば多項式時間で見つけられる、などの、下の"方針A"で書いてあるような話も触れられています。

だいぶ脱線してしまいました。問題を解きましょう。

方針A: 木には次数の少ないノードがある: O(N^4) ～ O(N^3)

審判団の解説で主に説明されている方針ですね。反転しまくって木が作れるとしたら、どれかのノードが葉（次数1）になるはずなので、

• どのノードが葉になるか全通り試してみる O(N)
  • それぞれの葉について、どのノードがその葉の親になるか全通り試してみる O(N)
    • 葉と親の候補が決まると全ノードの反転パターンが決まるので、実際に反転してみて木ができてるか調べる O(N^2)

とかやると木を全部列挙することができて、全体で O(N^4) と多項式時間で解けます。これだと最大ケース N=300 の時ちょっと遅いので、色々な工夫で計算量を落とせます。

• どのノードが葉になるか全通り試してみる O(N)
  • とりあえずそのノードの周りに辺がなくなるように周囲の頂点を反転しておく O(N^2)
  • ここで残っている辺を列挙。次のステップで辺の本数は最大N-1本しか変わらないので、この時点でグラフ全体で辺が 2N-1 本以上残っていたらもう木は作れない。continue;
  • それぞれの葉について、どのノードがその葉の親になるか全通り試してみる O(N)
    • 親候補ノードで反転すると候補グラフが得られる。O(N)
    • 辺が高々3N本しかないので木判定とか簡単に O(N) でできる

だとか、

• どのノードが葉になるか全通り試してみる O(N)
  • とりあえずそのノードの周りに辺がなくなるように周囲の頂点を反転しておく O(N^2)
  • ここで残っている辺のグラフの隣接リスト表現を作っておく
  • それぞれの葉について、どのノードがその葉の親になるか全通り試してみる O(N)
    • グラフ上をDFSして木になってるか判定（N本以上辺を辿ったら木でないので打ち切れるのでO(N)）、ただし親候補周辺の辺を反転した新しいグラフを毎回つくっていると遅いので、親頂点の周りだけ擬似的に反転したつもりになって辿る辺を反転してDFSする

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

static const int INF = 0x3fffffff;

int solve(int N, const vector<vector<int>>& Cost, const vector<vector<bool>>& Edge) {
	int best = INF;
	// 葉候補を全通り試す
	for(int leaf=0; leaf<N; ++leaf) {
		// leaf の周りに辺がなくなるように辺を反転してみる。
		// 隣接リスト表現のグラフをここで作っておく
		vector<vector<int>> G(N);
		for(int x=0; x<N; ++x)
		for(int y=x+1; y<N; ++y)
			if(Edge[x][leaf] ^ Edge[y][leaf] ^ Edge[x][y]) {
				G[x].push_back(y);
				G[y].push_back(x);
			}

		// 親候補を全通り試す
		for(int parent=0; parent<N; ++parent) if(parent!=leaf) {
			// parentの隣接ノード（G[u]を反転したもの）
			vector<int> neighbor_p; {
				vector<bool> gp(N);
				for(int y: G[parent]) gp[y] = true;
				for(int y=0; y<N; ++y) if(y!=parent && !gp[y])
					neighbor_p.push_back(y);
			}

			// DFSで木になっているか、その場合のコストを計算
			vector<bool> visited(N);
			function<int(int,int)> checktree = [&](int pre, int x){
				if(visited[x])
					return INF;
				visited[x] = true;

				int cost = 0;
				// 隣接辺をたどる。x==parentやy==parentの時だけ反転。
				// neighbor_p側からいずれたどるので、G[x]にparentが含まれてない
				// とき逆にparentを探索する…という処理は必要ないはず
				for(int y: (x==parent ? neighbor_p : G[x])) if(y!=pre&&y!=parent) {
					int r = checktree(x, y);
					if(r == INF)
						return INF;
					cost += Cost[x][y] + r;
				}
				return cost;
			};
			visited[leaf] = true;
			const int r = Cost[leaf][parent] + checktree(leaf, parent);
			if(count(visited.begin(),visited.end(),true) == N)
				best = min(best, r);
		}
	}
	return (best==INF ? -1 : best);
}

int main() {
	for(int N; cin>>N,N; ) {
		vector<vector<int>>  Cost(N, vector<int>(N));
		vector<vector<bool>> Edge(N, vector<bool>(N));
		for(int i=0;   i<N; ++i)
		for(int k=i+1; k<N; ++k) {
			int e; cin>>e;
			Cost[i][k] = Cost[k][i] = (e>0 ? e : -e);
			Edge[i][k] = Edge[k][i] = (e>0);
		}
		cout << solve(N, Cost, Edge) << endl;
	}
}

などで O(N^3) 時間に落ちます。

方針A': 木には次数の少ないノードがある: 乱択 O(N^2)

wataさんに聞いた解法。次数1のノードは少ないときは2個しかないかもしれないので全通り試してみることになりますが、「木の半分は次数2以下のノード」という性質もあります。

• ランダムに1点選ぶ
  • 次数1になるように反転するやりかた全通り試す
  • 次数2になるように反転するやりかたも全通り試す

で、木が作れるならば50%以上の確率でそれが見つかります。何回か繰り返せばほぼ確実に見つかります。ナイーブに実装すると N^3 の時間がかかるようにも見えますが、辺の本数が最終的にN-1になるという条件を考えて、反転相手の次数で枝を刈ることができて、次数2の場合については定数通りしか試さなくてよいことが言えたりします。

方針B: 木にはサイクルがない: O(N^3)

別の方針として、真っ向から枝刈り探索するという手もあります。O(N^4)くらいでしか自分では抑えられていませんでしたがchokudaiさんのツイートを見てO(N^3)が言える気がしてきました。擬似コードで書くと

int rec(int v) {
  if(v==N) return ペナルティの総和
  if(点{0..v-1}の間の辺でサイクルができてたら) return もう無理

  int a = rec(v+1);
  頂点vの周りを反転してみる;
  int b = rec(v+1);
  頂点vの周りを反転したのを元に戻す;
  return min(a,b);
}

return rec(0);

頂点vの反転をどちらにするか探索しようとしている時点で、{0..v-1}の間に張られる辺は確定しています。ここでサイクルができていたら最後まで探索しても木にはならないので即座に打ち切れますね。もう少し深く考えるとこの枝刈りはすごくて、

• {0..v-1} に一本も辺がない場合: vを反転するかしないか、どちらの可能性もありうる。
• {0..v-1} の中に辺が一本 a-b ある場合:
  • v-a と v-b 両方に辺があるなら、vでは反転するしかない。でないとサイクルができてしまう
  • v-a と v-b 両方に辺がないなら、vでは反転しない。
  • v-a と v-b の片方だけに辺があるなら、どちらの可能性があり得るが、いずれにせよ v-a-b という二辺繋がった形ができる
• {0..v-1} の中に a-b-c と二辺繋がった形がある場合:
  • サイクルができないようにするには、vで反転するかしないか、どちらかしかない

つまり探索途中に辺が一つでも確定してしまうと、その先にはあと2通りしか木の作り方がありません。どこで最初の辺を加えるか高々N通りの分岐と掛け合わせても、2N通りの葉しか探索しない探索木になります。

方針B': 木にはサイクルがない: O(N^2)

kawateaさんに聞いた解法。上の方針を全探索風ではなくてもっと決定的にすることができます。

• 頂点0の周りの辺が0本になるように反転
• もしこの時グラフ全体から完全に辺が消えていたら、
  • 頂点一つ押して反転して作れるスター型の木N通り、が作れる全域木の全て。
• もしグラフに辺 a-b が残っていたら、0,a,bをどう反転しても、三角形0-a-bには奇数本(1本か3本)の辺が残る。
  • 3本の場合はサイクルになってしまうので木にはならない
  • 1本の場合、上の方針Bの議論で書いたように、それぞれあと2通りしか木は作れない。
  • 合わせるとこの6通りを全部試せばよい