AOJ1238 True Liars

問題リンク True Liars

• 概要

P1人の正直者とP2人の嘘つきがいる。正直者は常に真実を言って、嘘つきは常に嘘を言う。
P1+P2人のうち、正直者はどの人物達かを特定したい。
X番の人物に問いかけ、「Y番の人は正直者か」という質問をN回する。X番の人物の返答は"yes" or "no"である。質問の返答に矛盾があるようなことは無い。
質問の内容から、正直者の人物を昇順に出力せよ。正直者を一意に特定できない場合はその旨を出力せよ。
0 <= N < 1000
0 <= P1, P2 <= 300

• 解法

3段階に分けて解きました。グルーピング→DP→DPからの解の復元 の流れです。
まず、質問から分かることですが、YESと返答した場合、XとYは同じ種族で、NOの場合、XとYは違う種族であるということが分かります。よって、人物を頂点としたグラフを考えます。グラフはいくつかの連結成分に分かれ、頂点を2色で色塗りすると、塗った色の数のペアを得ることができます。例えば、最後のサンプルで、1〜3の人物の連結成分だと(1, 2)、4〜7の人物の連結成分だと(1, 3)という具合です。得られたペアのうち、片方の数字を正直者の人数とすると、「和がP1になるようなペアのリストの数字の取り方」を考えればいいことになります。先の例でいうと、P1は4なので、(1, 2)のペアからは1、(1, 3)のペアからは3を採用すると和が4になり、なおかつこれが唯一の振り分け方なので、正直者が一意に特定できます。この振り分け方はDPで求めることができます。
dp[i][j]: i番目の森の連結成分までを考え、正直者がj人になるような割り振り方の数
この表を埋め、最終的にdp[last][P1]が1になっていれば正直者が一意に特定できます。
正直者が特定できる場合は、正直者の人物の番号をリストアップしなければなりません。
これはDP表から解を復元することができます。dp[last][P1]からdp[0][0]まで、その値が1になっているところをさかのぼればOKです。さかのぼり方を見れば、ペアのうちどちらの数字を採用したのかが分かるからです。グルーピングするときに、復元のために使う情報を各頂点に付与しておくといいと思います。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

//True Liars
public class AOJ1238 {

	int m, p1, p2, n, c1, c2, idx;
	Set<Integer>[] yes, no;
	boolean[] u;
	int[] id, mark;
	
	void f(int k, int x){
		if(u[k])return;
		if(x==0)c1++;
		else c2++;
		u[k] = true;
		id[k] = idx;
		mark[k] = x;
		for(int v:yes[k])f(v, x);
		for(int v:no[k])f(v, 1-x);
	}
	
	class R{
		int s, t;
		public R(int s, int t) {
			this.s = s;
			this.t = t;
		}
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		yes = new Set[600];
		no = new Set[600];
		u = new boolean[600];
		id = new int[600];
		mark = new int[600];
		for(;;){
			m = sc.nextInt(); p1 = sc.nextInt(); p2 = sc.nextInt();
			if((m|p1|p2)==0)break;
			n = p1+p2;
			for(int i=0;i<n;i++){
				yes[i] = new HashSet<Integer>();
				no[i] = new HashSet<Integer>();
			}
			while(m--!=0){
				int s = sc.nextInt()-1, t = sc.nextInt()-1;
				String r = sc.next();
				if("yes".equals(r)){
					yes[s].add(t); yes[t].add(s);
				}
				else{
					no[s].add(t); no[t].add(s);
				}
			}
			Arrays.fill(u, false);
			Arrays.fill(id, 0);
			Arrays.fill(mark, 0);
			List<R> list = new ArrayList<R>();
			idx = 0;
			for(int i=0;i<n;i++){
				c1 = c2 = 0;
				f(i, 0);
				if(0<c1+c2){
					idx++;
					list.add(new R(c1, c2));
				}
			}
			int N = list.size();
			int[][] dp = new int[N+1][p1+1];
			dp[0][0] = 1;
			for(int i=1;i<=N;i++){
				R r = list.get(i-1);
				for(int j=0;j<=p1;j++){
					if(r.s<=j)dp[i][j]+=dp[i-1][j-r.s];
					if(r.t<=j)dp[i][j]+=dp[i-1][j-r.t];
				}
			}
			if(dp[N][p1]!=1){
				System.out.println("no"); continue;
			}
			List<Integer> res = new ArrayList<Integer>();
			for(int i=N-1;i>=0;i--){
				R r = list.get(i);
				if(r.s<=p1 && dp[i][p1-r.s]==1){
					p1-=r.s;
					for(int j=0;j<n;j++)if(id[j]==i&&mark[j]==0)res.add(j);
				}
				else{
					p1-=r.t;
					for(int j=0;j<n;j++)if(id[j]==i&&mark[j]==1)res.add(j);
				}
			}
			Collections.sort(res);
			for(int x:res)System.out.println(x+1);
			System.out.println("end");
		}
	}
	
	public static void main(String[] args) {
		new AOJ1238().run();
	}
}