TopCoder SRM 820 : Div1 Medium LogarithmCircuit

本番出てたら、時間内にこれ詰め切れてたかなぁ…？
https://community.topcoder.com/stat?c=problem_statement&pm=17347

問題

ある論理回路を考える。
各線には0/1のいずれかの値(に対応する電流)が流れる。
入力線がN個あり、これでN bitの値Xが入力されたとする。

or/and/xor/nandのゲートを利用し、floor(log(X))を出力せよ。
ただし、回路の数は200個以下で、ある入力から出力までに12個以上のゲートを経由してはならない。

解法

Nがいろいろあると面倒なので、まずNをそろえよう。
以下のコードでは、同じ入力線2本をxorゲートに入れれば必ず0が出力されるので、まずN=20に揃える。
以下、X[i] := Xのi bit目の値 と表現する。

手順としては以下の通り。

• YをXのMSB以下の全bitをXとしたものにする。
  • ORゲートを(N-1)並べ、Y[i]＝Y[i+1] or X[i] を順次求めれば達成できるが、この場合経由するゲート長制限に引っかかる。
  • そこで、Y[i] |= Y[i+2^k]のような感じでlog(N)回畳み込む感じの処理を行うと、ゲート数はO(NlogN)個になるが、経由するゲート長はO(logN)で済む。
• ZをYのMSB未満の全bitを0にしたものにする
  • これはZ[i]=Y[i] xor Y[i+1]なので、ゲート数O(N)、経由するゲート長O(1)で処理できる。
• ZのMSBの位置を、2進数表現Wにする。
  • Z[m*(2^k)]がいずれかのmで1なら、W[k]=1となるようにする。これも畳み込む感じで行えば、経由するゲート長はO(logN)で済む。

class LogarithmCircuit {
	public:
	vector <int> construct(int N) {
		vector<vector<int>> R;
		
		int nex=N;
		int i,j;
		vector<int> C;
		FOR(i,20) {
			if(i<N) {
				C.push_back(i);
			}
			else {
				R.push_back({49,0,0});
				C.push_back(nex++);
			}
		}
		N=20;
		int step=1,d=0;
		for(int step=1;step<=N;step*=2) {
			d++;
			vector<int> C2;
			FOR(i,N) {
				if(i+step<N) {
					R.push_back({47,C[i],C[i+step]});
					C2.push_back(nex++);
				}
				else {
					C2.push_back(C[i]);
				}
			}
			C=C2;
		}
		
		vector<int> D;
		FOR(i,N-1) {
			R.push_back({49,C[i],C[i+1]});
			D.push_back(nex++);
		}
		D.push_back(C.back());
		
		
		vector<int> O;
		FOR(i,d) {
			queue<int> cand;
			FOR(j,D.size()) if(j&(1<<i)) cand.push(D[j]);
			while(cand.size()>=2) {
				int a=cand.front();
				cand.pop();
				int b=cand.front();
				cand.pop();
				R.push_back({47,a,b});
				cand.push(nex++);
			}
			O.push_back(cand.front());
		}
		
		vector<int> ret;
		ret.push_back(R.size());
		FORR(r,R) {
			ret.push_back(r[0]);
			ret.push_back(r[1]);
			ret.push_back(r[2]);
		}
		ret.push_back(O.size());
		FORR(o,O) ret.push_back(o);
		return ret;
	}
}

まとめ

これはシミュレータが欲しくなる問題。