Codeforces #941 : Div1 B. Missing Subsequence Sum

あまり出来の良くなかった回。
https://codeforces.com/contest/1965/problem/B

問題

整数N,Kが与えられる。
25要素以下の整数のうち、部分列として和がKとなるものは作れないが、K以外の1～Nはすべて作れるようにせよ。

解法

Nは上限の10^6固定で考えてよい。
まず和がKに到達しない範囲で1,2,4,8...,2^xと追加していこう。
そうすると1～2^xの和をVとすると、V+W=R-1となるようなWを追加すれば、1～K-1はすべて作ることができる。
ここにK+1と2*K+1を加えれば、K+1～3*Kを作ることができる。
あとは倍々ゲームの要領で大きな値を追加し、構成できる最大値を増やしていこう。

int T,N,K;

void verify(vector<int> a,int n,int k) {
	set<int> S;
	int mask,i;
	FOR(mask,1<<a.size()) {
		int sum=0;
		FOR(i,a.size()) if(mask&(1<<i)) sum+=a[i];
		S.insert(sum);
	}
	/*
	for(i=1;i<=n;i++) {
		cout<<S.count(i);
	}
	cout<<endl;
	*/
	for(i=1;i<=n;i++) {
		assert(S.count(i)==(i!=k));
	}
	assert(a.size()<=25);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		vector<int> ret;
		int L=0,R=0;
		int L2,R2;
		N=1000000;
		if(K==1) {
			ret.push_back(2);
			ret.push_back(3);
			L2=2,R2=3;
		}
		else if(K==2) {
			ret.push_back(1);
			ret.push_back(3);
			ret.push_back(4);
			ret.push_back(5);
			L2=3,R2=5;
		}
		else if(K==3) {
			ret.push_back(1);
			ret.push_back(1);
			ret.push_back(4);
			ret.push_back(5);
			ret.push_back(6);
			ret.push_back(7);
			L2=4,R2=7;
		}
		else if(K==4) {
			ret.push_back(1);
			ret.push_back(2);
			ret.push_back(5);
			ret.push_back(8);
			L2=5,R2=11;
		}
		else {
			while(R<K) {
				if(R+R+1<K) {
					ret.push_back(R+1);
					R=2*R+1;
				}
				else {
					ret.push_back(K-R-1);
					R=K-1;
					break;
				}
			}
			ret.push_back(K+1);
			ret.push_back(2*K+1);
			L2=K+1;
			R2=R+K+K+1;
		}
		while(R2<N) {
			ret.push_back(R2+1-L2);
			R2+=R2+1-L2;
		}
		
		cout<<ret.size()<<endl;
		FORR(r,ret) cout<<r<<" ";
		cout<<endl;
		//verify(ret,N,K);
	}
}

まとめ

verify関数をわざわざ作るなど、本番かなり丁寧に取り組んでるな…。