二部マッチング

前から最大流問題を解いてみたいなーを思っており、蟻本を購入したのをきっかけに、この前参加したFacebook Hacker Cup 2013 Round 1の2問目「Security」が二部マッチングの問題だったので解いてみました。

Security

{a, b, c, d, e, f}からなるキー k がある。kはmのセクションから成っている。

関数 f : kを引数にし、いくつかの文字を?にする
関数 g : kを引数にし、kをセクションで分けて順番を変える。

m, k1 = f(k), k2 = f(g(k)) が与えられるので、考えられるkの中で辞書順最小のものを求めよ。

本番は手も足も出ませんでしたが、解説(https://www.facebook.com/notes/facebook-hacker-cup/2013-round-1-solutions/606859202663318)によるとk1の各セクションとk2の各セクションをノードにして、二部マッチングを行えばいいそうです。

二部マッチングは最大流問題に帰着でき、さらにその構造からさらに簡単に書けます。
アルゴリズムとしては、マッチングできるものを適当にマッチングしていき、やってるうちに無理が出てきたら前のマッチングをやり直してみるという感じのようです。O(|E||V|)。

蟻本を写経して作成。

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;

public class R1_2013_B {
	static Vector<Integer>[] edge;
	static int[] match;
	static boolean[] used;
	static int v, m;
	static char[][] k1s, k2s;

	public static void main(String[] args) {
		doIt();
	}

	static void doIt() {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			m = sc.nextInt();
			String k1 = sc.next();
			String k2 = sc.next();
			int sec = k1.length() / m;
			k1s = new char[m][sec];
			k2s = new char[m][sec];
			for (int j = 0; j < m; j++) {
				k1s[j] = k1.substring(sec * j, sec * j + sec).toCharArray();
				k2s[j] = k2.substring(sec * j, sec * j + sec).toCharArray();
			}
			v = 2 * m;
			edge = (Vector<Integer>[]) new Vector[v];
			for (int j = 0; j < v; j++) edge[j] = new Vector<Integer>();
			match = new int[2 * m];
			used = new boolean[2 * m];
			
			if(m != bipartite_matching()){
				System.out.println("Case #" + (i + 1) + ": IMPOSSIBLE");
			}
			else{
				String ans = "";
				for (int j = 0; j < m; j++) {
					String s = "";
					for (int k = 0; k < sec; k++) {
						if(k1s[j][k] == '?'){
							for(char c = 'a'; c <= 'f';c++){
								k1s[j][k] = c;
								if(m == bipartite_matching()){s += c;break;}
							}
						}
						else s += k1s[j][k];
					}
					ans += s;
				}
				System.out.println("Case #" + (i + 1) + ": "  + ans);
			}
		}
	}
	static int bipartite_matching(){
		for (int j = 0; j < v; j++) edge[j].clear();
		for (int j = 0; j < m; j++) {
			for (int j2 = 0; j2 < m; j2++) {
				if(cmp(k1s[j], k2s[j2])){
					edge[j].add(m + j2);
					edge[m + j2].add(j);
				}
			}
		}
		
		Arrays.fill(match, -1);
		int res = 0;
		for (int j = 0; j < v; j++) {
			if(match[j] == -1){
				Arrays.fill(used, false);
				if(dfs(j)) res++;
			}
		}
		return res;
	}
	static boolean cmp(char[] a, char[] b){
		for (int i = 0; i < a.length; i++) {
			if(a[i] != '?' && b[i] != '?' && a[i] != b[i]) return false;
		}
		return true;
	}
	static boolean dfs(int v0){
		used[v0] = true;
		for (int i = 0; i < edge[v0].size(); i++) {
			int u = edge[v0].get(i);
			int w = match[u];
			if(w == -1 || used[w] == false && dfs(w)){
				match[v0] = u;
				match[u] = v0;
				return true;
			}
		}
		return false;
	}
}

知らなかったのがfor文を下のようにcharで回せること。出来るんだろうなーとは思ってましたが、初めて実装しました。

for(char c = 'a'; c <= 'f';c++) ;

あとJavaにおけるVectorの配列の作り方。こちら(http://tyche.pu-toyama.ac.jp/~ko-ji/now-java/VectorArray.html)を見たところ、いまいち綺麗な解決策がないようです。
仕方ないので、以下のように一番簡単に実装。でも、コンパイル時に警告が出ます。

Vector<Integer>[] edge = (Vector<Integer>[]) new Vector[v];

うーん、なんかすっきりしない。

そのうち最大流問題、最小流問題もやってみます。