yukicoder : No.1589 Bit Vector

★4の中では簡単かも。
https://yukicoder.me/problems/no/1589

問題

(N+1)要素の数列Bがある。各要素は0か1の値を取る。
B[0]～B[N-1]の値が与えられたとき、以下の操作を行うことができるとする。
Bの値が何であれ、B[N]に「B[0]～B[N-1]中に1がK個以上あるか？」を示す値が入るような操作列を示せ。

• B[i] = x と値を上書きする
• B[i] = B[j] xor B[k]
• B[i] = B[j] and B[k]

解法

Bを降順ソートし、B[K-1]をB[N]にコピーすればよい。
そこで、Bを降順ソートすることを考えよう。

2値B[i],B[i+1]を降順に並べるには、B[N]をバッファとして使うと以下の5手で行える。

• B[N] = B[i] and B[i+1]
• B[i] = B[i] xor B[i+1]
• B[i+1] = 1
• B[i+1] = B[i+1] and B[N]
• B[i] = B[i] xor B[N]

あとはこの2値ソートをバブルソートの要領で繰り返せばよい。

int N,K;
int T;
int B[55];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	int num=2;
	FOR(x,N) {
		for(y=N-2;y>=x;y--) {
			num+=5;
		}
	}
	cout<<num<<endl;
	
	FOR(x,N) {
		for(y=N-2;y>=x;y--) {
			cout<<"AND "<<N<<" "<<y<<" "<<y+1<<endl;
			cout<<"XOR "<<y<<" "<<y<<" "<<y+1<<endl;
			cout<<"UPD "<<y+1<<" 1"<<endl;
			cout<<"AND "<<y+1<<" "<<y+1<<" "<<N<<endl;
			cout<<"XOR "<<y<<" "<<y<<" "<<N<<endl;
		}
	}
	
	cout<<"UPD "<<N<<" 1"<<endl;
	cout<<"AND "<<N<<" "<<N<<" "<<(K-1)<<endl;
	
	
}

まとめ

どこらへんが典型なんだろ。