読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Gather the Maps!(AOJ No.2011)

Gather the Maps!(AOJ No.2011)

子孫の数nと子孫 0,1, \cdots , n-1のフリーな日の予定表が与えられる。
はじめ、各人は、個人の地図を持っている。
各人は、フリーな日にフリーな人にあって、持っている地図を渡すことができる。
子孫の内のだれかがn枚の地図を所有するのに(初期状態を1日目として)必要最低限の日にちをこたえる。
30日を超える場合は-1と答える。
制約
 1 < n \leq 50

アルゴリズム

はじめに子孫 iが持っている地図を地図 m_i
 DP_{i,j}を子孫 i j日目に所有可能な地図の集合、
 f_j j日目にフリーな子孫の集合とする。
 DP_{i,0} = \{m_i \}で初期化。
 0\leq i < n, 1\leq j \leq 30について、
 DP_{i,j} = \left\{ \begin{array}{ll} DP_{i,j-1} & (i\not\in f_j ) \\ \bigcup_{k\in f_j} DP_{k , j-1} & (otherwise) \end{array} \right.
を計算。
答えは、{ \min \{ j \left | 0\leq i < n, 0 < j \leq 30, |DP_{i,j}|=n \right \} }
計算量は、i,jのループ O(dn)×集合のマージ(フリーな子孫の数) O(n) = O(dn^2)
 1 \leq d \leq 30, 1 < n \leq 50なので、30×50×50 = 75000

コード

HashSetの元配列を使おうとするとなんかコンパイルエラーになったので、
@SuppressWarnings("unchecked")で無視するようにしたら通った。

import java.util.*;
public class aoj2011 {
	static Scanner stdin;
	static final int D = 30;
	public static void main(String[] args) {
		stdin = new Scanner(System.in);
		new aoj2011();
	}
		int solve(boolean[][] f, int n){
		@SuppressWarnings("unchecked") //多分↓のnewで<>を指定しないため警告がでる AOJではCompileErrorになるので、無視するようにした
		HashSet<Integer>[] DP = new HashSet[n];//new HashSet<Integer>[n]とすると総称配列を作れないと怒られる
		for(int i=0; i<n; ++i){
			DP[i] = new HashSet<Integer>();
			DP[i].add(i);
		}
		for(int j=1; j<D+1; ++j){
			HashSet<Integer> temp = new HashSet<Integer>(); //今日フリーな人がシェアできる地図の集合
			for(int i=0; i<n; ++i){
				if( f[i][j] ){
					temp.addAll(DP[i]);
					if(temp.size() == n) return j;
					DP[i] = temp; //フリーな人の地図の集合tempを参照
				}
			}
		}
		return -1;
	}
	aoj2011(){
		while(true){
			int n = stdin.nextInt();
			if(n==0) break;
			boolean[][] f = new boolean[n][D+1];
			for(int i=0; i<n; ++i){
				int m = stdin.nextInt();
				while(m-- >0) f[i][stdin.nextInt()] = true;
			}
			System.out.println( solve(f, n) );
		}
	}
}