TopCoder SRM 689 Div1 Medium MultiplicationTable3

constructionゲー多いな…。
https://community.topcoder.com/stat?c=problem_statement&pm=14244

問題

整数0～(N-1)から構成される集合Sの要素に対する二項演算子$を考える。
この二項演算子の結果は２次元テーブルとして表現され、その結果はやはりS中の要素(すなわち0～(N-1)の整数)となる。

Sの空でない部分集合Tのうち、T中の２要素に$を適用した場合の結果がTに収まるようなものがちょうどx個になるようにしたい。
そのようなN及び結果テーブルを構築せよ。

解法

空集合も合わせて計(x+1)個が条件を満たすようなテーブルOを構築しよう。
Case#3が示すように、x $ y = xとなるテーブルを構築すると、(空集合合わせ)2^N個の条件を満たす部分集合を構築することができる。

(x+1)を２進数表記したときの最上位桁を(0-indexedで)d bit目とする。
まずd個分の要素は上の方法でテーブルを作ると、2^d個分の部分集合を作成できる。

あとは(x+1)を2進数表記したとき、d bit未満の位置で立っているビットbに対し、2^b個部分集合を追加できるテーブルを構築しよう。
ここまで作成した要素数をeとする。
eを用いるときは、0～(d-1)のd個の要素のうち、0～(b-1)のb要素は含んでも含まなくても良く、b～(e-1)は必ず含まないといけないようにすれば、2^b個部分集合を追加できる。
よって以下のようにするとよい。

• i＜bの時O(i,e) = i
• b≦i＜eの時O(i,e) = i+1
• i=eの時O(i,e) = b

以下のコードはチェック用のコードも含んでいる。

class MultiplicationTable3 {
	public:
	int check(vector <int> v)  {
		int N=1;
		int ret=0,x,y;
		while(N*N<v.size()) N++;
		for(int mask=1;mask<1<<N;mask++) {
			int ok=1;
			FOR(y,N) if(mask&(1<<y)) FOR(x,N) if(mask&(1<<x)) if((mask & (1<<v[y*N+x]))==0) ok=0;
			ret+=ok;
		}
		return ret;
	}
	vector <int> construct(int X) {
		int y=X+1;
		vector<int> V,R;
		int i,x;
		for(i=10;i>=0;i--) if(y&(1<<i)) V.push_back(i);
		int sz=V[0]+V.size()-1;
		
		R.resize(sz*sz);
		
		FOR(i,V[0]) FOR(x,sz) R[i*sz+x]=x;
		int cur=V[0];
		for(i=1;i<V.size();i++) {
			FOR(x,sz) {
				if(x==cur) R[cur*sz+x]=V[i];
				else if(x>=cur || x<V[i]) R[cur*sz+x]=x;
				else R[cur*sz+x]=x+1;
			}
			cur++;
		}
		
		//assert(check(R)==X);
		return R;
	}
}

まとめ

かなり手間取ったけど、本番チェック関数もちゃんと使い確信をもって通せたので良かった。