本番出てたら、時間内にこれ詰め切れてたかなぁ…?
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; } }
まとめ
これはシミュレータが欲しくなる問題。