Codeforces #1082 : Div1 B. Recollect Numbers

問題

整数N,Kが与えられる。
1～Nのカードが２枚ずつ、計2N枚のカードで神経衰弱をする。
最適な手順で端からカードをめくったとき、めくる回数がK組となるカードの並びを答えよ。

解法

N枚に対し、めくる回数は最小はN組、最大(2N-1)組となる。
ここから再帰的にNを下げていこう。

• K=2N-1のとき、1,2,3,2,4,3,5,4,....,N,1と配置すると(2N-1)組かかる。
• K＜2N-1の時、末尾に２枚をNにすると、N,Kを1小さい状態にできる。

int T,N,K;
int A[606060];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		int L=N,R=2*N-1;
		if(K<L||K>R) {
			cout<<"NO"<<endl;
			continue;
		}
		vector<int> V;
		while(N) {
			int L=N,R=2*N-1;
			
			if(K>L&&K<R) {
				V.push_back(N);
				V.push_back(N);
				N--;
				K--;
			}
			else if(K==L) {
				V.push_back(N);
				V.push_back(N);
				N--;
				K--;
			}
			else {
				V.push_back(1);
				V.push_back(2);
				for(x=3;x<=N;x++) {
					V.push_back(x);
					V.push_back(x-1);
				}
				V.push_back(N);
				V.push_back(1);
				K=N=0;
			}
		}
		assert(K==0);
		cout<<"YES"<<endl;
		FORR(a,V) cout<<a<<" ";
		cout<<endl;
		
	}
}

まとめ

ここら辺はまだよかったんだけどな。