AOJ1302 Twenty Questions

AOJ Volume13

問題リンク Twenty Questions

  • 概要

M個の特徴のみからなる世界がある。ここにN個の物体があり、お互いに全く同じ特徴のものはない。今手元にN個の物体のうちの1つがあり、これが何か特定したい。そのために、人に特徴のうちの1つを聞くことができる。聞いた内容から次に聞く内容を決めてよい。物体を特定するために必要な手数の最悪手数を最小化せよ。
1 <= M <= 11
1 <= N <= 128

  • 解法

N個の物体のうち、これまで質問の内容から可能性が残っている物体の集合をSとします。
特徴jについて質問すると、yesの場合とnoの場合に分かれ、Sのうちで、jの特徴がyesのものとnoのものとで更にグループ化することができます。

Sが1個以下になれば特定完了です。そうでなければ、yesの場合とnoの場合を試し、（最悪の場合なので）両者のうちの大きい方の手数+1がSに対する手数になります。更に、特徴jについて聞かないという選択肢もあるのでこれも調べます。よって、特徴1つについて3通りの選択肢があるので、O(3^M)で解けるわーっと思ったんですがWAです。（つまりこれは解法ではない）

この後も色々試したのですがギブアップして解法を調べました。
メモ化DPで解けるようです。
mem[ 質問した特徴の集合 ][ その中でyesとなった特徴の集合 ] -> これらの情報から物体を特定するための最小手数
という表を埋めます。
O(3^M)の再帰の方法と違うところは、可能性が残っている物体の集合Sに対して、次に質問する特徴は、まだ質問していない物のうちのどれか1つということです。再帰だと、再帰の引数jの特徴についてのみ尋ねることになります（jについて質問しなければ更にその先）。この両者の違いで、答えが変わるのがピンと来ないです。変わっているのは質問する順番だと思うんですが、順序って関係無い気がしてならないです。
うーむ...

※追記
あ、分かったかも。
「聞いた内容から次に聞く内容を決めていい」からかな。
聞いた内容＝これまでに質問した結果ってことで、次に聞く質問の候補はまだ質問してないうちのどれかになるのか。そんな気がしてきた。

  • ソース
import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;

//Twenty Questions
public class AOJ1302 {

	int n, m;
	int[] s;
	BitSet[] yes, no;
	int[][] mem;
	
	int f(int S, int SY){
		if(mem[S][SY]!=-1)return mem[S][SY];
		int res = m;
		BitSet bs = new BitSet(n);
		bs.set(0, n, true);
		for(int j=0;j<m;j++)if(((S>>j)&1)>0){
			if(((SY>>j)&1)>0)bs.and(yes[j]);
			else bs.and(no[j]);
		}
		if(bs.cardinality()<=1)return mem[S][SY] = 0;
		for(int j=0;j<m;j++)if(((S>>j)&1)==0){
			res = Math.min(res, Math.max(f(S|1<<j, SY|1<<j), f(S|1<<j, SY))+1);
		}
		return mem[S][SY] = res;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		mem = new int[1<<11][1<<11];
		for(;;){
			m = sc.nextInt(); n = sc.nextInt();
			if((m|n)==0)break;
			s = new int[n];
			yes = new BitSet[m];
			no = new BitSet[m];
			for(int i=0;i<m;i++){
				yes[i] = new BitSet(n);
				no[i] = new BitSet(n);
			}
			for(int i=0;i<n;i++){
				s[i] = Integer.parseInt(sc.next(), 2);
				for(int j=0;j<m;j++){
					if(((s[i]>>j)&1)==0)no[j].set(i, true);
					else yes[j].set(i, true);
				}
			}
			for(int[]m:mem)Arrays.fill(m, -1);
			System.out.println(f(0, 0));
		}
	}

	public static void main(String[] args) {
		new AOJ1302().run();
	}
}