AtCoder ARC #206 : D - LIS ∩ LDS

だいぶ手間取った…。
https://atcoder.jp/contests/arc206/tasks/arc206_d

問題

整数N,Kが与えられる。
1～NのPermutationのうち、LISにもLDSにも入りうる要素がちょうどK個となるようなものがあれば一例を答えよ。

解法

• K≧2の場合
  • 1,2,3,...,N-K,N,N-1,N-2,...N-K+1とすると、どれもLISには含まれうるが、LDSに含まれるのはN～(N-K+1)のK要素だけになる。
• K=1の場合
  • N=1の時は明らか
  • N=2～4の時解なし
  • N≧5の時、2,3,4...,N-3,N,N-2,1,N-1とすると、(N-2)だけがLISにもLDSにも含まれる。
• K=0の場合
  • N＜8の時解なし
  • N≧8の時、3,4,N,N-1,2,1,5,6,....,N-2とすると、LISは3,4,...,N-2、LDSはN,N-1,2,1となって両方に含まれる要素がなくなる。

int T,N,K;

int hoge(vector<int> V) {
	int mask;
	int N=V.size();
	int ma=0,mi=0;
	int i;
	FOR(mask,1<<N) if(__builtin_popcount(mask)>ma) {
		int pre=-1;
		FOR(i,N) if(mask&(1<<i)) {
			if(V[i]<pre) break;
			pre=V[i];
		}
		if(i==N) ma=__builtin_popcount(mask);
	}
	FOR(mask,1<<N) if(__builtin_popcount(mask)>mi) {
		int pre=100;
		FOR(i,N) if(mask&(1<<i)) {
			if(V[i]>pre) break;
			pre=V[i];
		}
		if(i==N) mi=__builtin_popcount(mask);
	}
	int ret1=0,ret2=0;
	FOR(mask,1<<N) if(__builtin_popcount(mask)==ma) {
		int pre=-1;
		FOR(i,N) if(mask&(1<<i)) {
			if(V[i]<pre) break;
			pre=V[i];
		}
		if(i==N) ret1|=mask;
	}
	FOR(mask,1<<N) if(__builtin_popcount(mask)==mi) {
		int pre=100;
		FOR(i,N) if(mask&(1<<i)) {
			if(V[i]>pre) break;
			pre=V[i];
		}
		if(i==N) ret2|=mask;
	}
	return ret1&ret2;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	/*
	vector<int> V={1,2,3,4,5,6,7,8,9};
	do {
		cout<<__builtin_popcount(hoge(V))<<endl;
		if(__builtin_popcount(hoge(V))==0) {
			FORR(v,V) cout<<v<<" ";
			cout<<endl;
		}
	} while(next_permutation(ALL(V)));
	return ;
	*/
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		if(K>=2) {
			FOR(i,N-K) cout<<i+1<<" ";
			for(i=N;i>N-K;i--) cout<<i<<" ";
			cout<<endl;
		}
		else if(K==0) {
			if(N<=7) {
				cout<<-1<<endl;
			}
			else {
				cout<<"3 4 ";
				cout<<N<<" "<<N-1<<" "<<2<<" "<<1<<" ";
				for(i=5;i<=N-2;i++) cout<<i<<" ";
				cout<<endl;
			}
		}
		else if(K==1) {
			if(N==1) {
				cout<<1<<endl;
			}
			else if(N>=5) {
				for(i=2;i<=N-3;i++) cout<<i<<" ";
				cout<<N<<" "<<N-2<<" "<<1<<" "<<N-1<<endl;
			}
			else {
				cout<<-1<<endl;
			}
		}
		
	}
}

まとめ

最初K=0の場合解なしと思ってて、いざ総当たりしたらN=8から解が出てきてびっくりした。