kmjp's blog

競技プログラミング参加記です

TopCoder SRM 681 Div2 Hard XorLists

SRM

Div1Hardより少し手間取った。
https://community.topcoder.com/stat?c=problem_statement&pm=14136

問題

n要素の数列Aがある。
各要素は0～mの間の整数である。

Aは明には与えられていないが、S[x][y] = A[x]^A[y]で計算された配列Sが与えられる。
Sに対し、条件を満たすAの組み合わせを求めよ。

解法

まずSの特性と矛盾する以下のケースを判定し、0を返そう。
以下はどんなAでも起きえないケースである。

  • S[x][x] != 0
  • S[x][y] != S[y][x]
  • S[x][y] ^ S[y][z] ^ S[y][z] != 0

上記条件をクリアしていれば、Aの1要素を決めればSから残り要素はすべて確定する。
あとは、Aの最大値がmを超ないケースのみを数え上げていこう。

2進数表記で上の桁から順に以下をDPなりメモ化再帰で求めていく。
f(d,mask) := (A[i]のうちmaskに該当する要素は下からd桁目以上がmと一致する。該当しない要素はmより小さい。そのようなAに対し条件を満たす組み合わせ数)
以下、桁番号dは0-originで計算している。

  • もしmask==0またはd＜0なら、d桁以下は各要素どんな値でもいいので、f(d,mask) = 2**(d+1)
  • そうでない場合
    • mのd桁目が0なら、maskに該当するA[i]のd桁目は0しか取りえない。
      • maskに該当する2要素x,yに対し、S[x][y]のd桁目が1となるものがあると矛盾するので、f(d,mask)=0
      • それ以外の場合、f(d,mask)=f(d-1,mask)
    • mのd桁目が1なら、maskに含まれるsubmaskを総当たりしよう。
      • maskに該当する要素xに対し、submaskにもxが含まれるならA[x]のd桁目は1、そうでないなら0と考える。後者を選んだ場合、以下の桁はなんでもよくなる。
      • maskに該当する2要素x,yに対し、S[x][y]のd桁目が、上記基準で選らんだA[x]^A[y]と一致しない場合のがあると矛盾するので、そのsubmaskのケースは無視する。
      • それ以外の場合、f(d,mask)+=f(d-1,submask)
int memo[40][2000];
int S[10][10];

class XorLists {
	public:
	int N,M;
	
	int hoge(int d,int mask) {
		if(d==-1) return 1;
		if(memo[d][mask]>=0) return memo[d][mask];
		if(mask==0) return 1<<(d+1);
		int& ret=memo[d][mask];
		ret=0;
		
		int x,y,smask;
		FOR(smask,1<<N) if((mask&smask)==smask) {
			if((M&(1<<d))==0 && smask!=0) continue;
			int ng=0;
			FOR(y,N) FOR(x,y) if((mask>>x)&(mask>>y)&1) if(((S[x][y]>>d)^(smask>>x)^(smask>>y))&1) ng++;
			if(ng==0) ret+=hoge(d-1,(M&(1<<d))?smask:mask);
		}
		return ret;
	}
	
	int countLists(vector <int> s, int m) {
		int x,y,z;
		M=m;
		N=sqrt(s.size()+0.1);
		
		if(*max_element(s.begin(),s.end())==0) return m+1;
		FOR(y,N) FOR(x,N) S[x][y]=s[x*N+y];
		FOR(x,N) if(S[x][x]) return 0;
		FOR(y,N) FOR(x,N) if(S[x][y]!=S[y][x]) return 0;
		FOR(x,N) FOR(y,N) FOR(z,N) if(S[x][y]^S[y][z]^S[x][z]) return 0;
		
		MINUS(memo);
		return hoge(30,(1<<N)-1);
	}
}

まとめ

xorネタ多いなぁ。