TopCoder SRM 653 Div1 Easy CountryGroupHard

最初問題の意図を読み間違えて無駄実装で時間食ったのが痛い。
http://community.topcoder.com/stat?c=problem_statement&pm=13688

問題

N人の人が一列に並んでいる。
各人はどこかの国の出身で、同じ国の出身者は固まっている。

数人に質問したところ、それぞれ列に並ぶ同じ国の人数A[i]を答えてくれた。
(質問を受けてない人はA[i]=0である)
これで誰が同じ国の出身か全員1通りに確定できるか答えよ。

なお、入力として情報不足で確定できない場合はありうるが、情報に矛盾があるケースはない。

解法

部分列A[L..R]内を1通りに確定できるかどうかをメモ化再帰で求める。

まず、A[L..R]が全員質問を受けていない(A[i]=0)場合、部分列の長さが2以上だとその人たちがどう分類されるか判定できず、2通り以上の組み合わせがありうる。
L=R、すなわち部分列の長さが1なら、その1人だけがその国の出身と確定する。

次に、A[L..R]中で質問に答えた人xがいる場合、A[x]=yとする。
まずA[L..R]中でA[x]を含む長さyの部分列を総当たりし、条件を満たすケースが0通りか1通りか2通り以上かを求める。
条件を満たすのは、A[x]を含む長さyの部分列中の要素がすべて0かyであり、かつその両側の部分列も再帰的に条件を満たす場合である。

後は全体で条件を満たすのが1通りのみかどうかを求める。

int memo[111][111];
class CountryGroupHard {
	public:
	int N;
	vector <int> A;
	int valid(int L,int R) {
		int i,x,y;
		int& ret=memo[L][R];
		if(R<=L) return 1;
		if(ret>=0) return ret;
		
		for(i=L;i<R;i++) if(A[i]) break;
		if(i==R) return ret=R-L;
		
		ret=0;
		for(x=i-A[i]+1;x<=i;x++) {
			int ng=0;
			for(y=x;y<x+A[i];y++) {
				if(y<L || y>=R) ng++;
				else if(A[y]!=0 && A[y]!=A[i]) ng++;
			}
			if(ng==0) ret += min(2,valid(L,x)*valid(x+A[i],R));
		}
		
		return ret;
	}
	
	string solve(vector <int> a) {
		int i,x=0;
		A=a;
		MINUS(memo);
		N=a.size();
		if(valid(0,N)==1) return "Sufficient";
		else return "Insufficient";
	}
}

まとめ

ちょっとややこしいけど面白い問題。