yukicoder : No.1820 NandShift

なるほど。
https://yukicoder.me/problems/no/1820

問題

沢山のM bitのカウンタBがある。
うち先頭N個の初期値が与えられる。それ以外のカウンタの初期値は0である。
以下の処理を1000回まで使用し、先頭のカウンタの値をXにせよ。

• B[x]をB[i]を1bit左シフトした値とする。
• B[x]をB[i] nand B[j]とする。

解法

(P nand P) nand (Q nand Q) = P or Qとなるので、orの処理は容易に行えるようになった。
そこで、1,2,4,....,2^(M-1)を頑張って作り、あとはorでそれらを組み合わせよう。

• B[x]=0のカウンタを用い、B[x]=B[x] nand B[x]=(2^M)-1を作る。
• B[y] = B[x]<<1より、B[y]=(2^M)-2を作る
• B[z] = B[x] nand B[y] = 1で1を作れる
• B[z]=1から、シフトを繰り返して2の累乗を作る
• あとはそれらの一部のorを取りXを作る。

int N,M;
string X;
ll V[300];

vector<vector<int>> ret;

void go_shift(int x,int i) {
	ret.push_back({1,x,i});
	V[x]=(V[i]<<1)&&((1LL<<M)-1);
}
void go_nand(int x,int i,int j) {
	ret.push_back({2,x,i,j});
	V[x]=(V[i]&V[j])^((1LL<<M)-1);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>X;
	
	// 101=2^M-1
	go_nand(101,101,101);
	// 102=2^M-2
	go_shift(102,101);
	
	// 200=1
	go_nand(200,101,102);
	for(i=1;i<M;i++) {
		// 200+i=2^i
		go_shift(200+i,200+i-1);
	}
	reverse(ALL(X));
	go_shift(0,199);
	FOR(i,M) {
		if(X[i]=='1') {
			go_nand(0,0,0);
			go_nand(200+i,200+i,200+i);
			go_nand(0,0,200+i);
		}
	}
	cout<<ret.size()<<endl;
	FORR(r,ret) {
		FOR(i,r.size()) {
			if(i) cout<<" ";
			cout<<r[i];
		}
		cout<<endl;
	}
}

まとめ

初期値を使わないってのがいいね。