yukicoder : No.2037 NAND Pyramid

この特性は知らなかった。
https://yukicoder.me/problems/no/2037

問題

ブロックがN段ピラミッド状に置かれている。
最下段の各ブロックには、0か1の値が書かれている。
下から2段目以降のブロックには、直下の2ブロックに書かれた値のNANDの値が書かれるとする。
最上段のブロックに書かれた値は何か。

解法

最初2段分だけ愚直に値を計算しよう。
以降は、各ブロックと2段上のブロックは同じ値になるので、最初計算した2段分の値をもとに算出できる。
詳細はEditorial参照。

int N,K;
string S;
int A[403030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	FOR(i,N) {
		A[i]=S[i]=='1';
	}
	FOR(i,N-1) A[i]=1-(A[i]&A[i+1]);
	N--;
	if((N-K)%2) {
		FOR(i,N-1) A[i]=1-(A[i]&A[i+1]);
		N--;
	}
	
	FOR(i,K) cout<<A[i+(N-K)/2];
	cout<<endl;
	
}

まとめ

ANDやXORに比べると、NANDを使う問題慣れないな…。