AtCoder ARC #091 : E - LISDL

1ミスはもったいないけど1時間で全完できたのはよかった。
https://beta.atcoder.jp/contests/arc091/tasks/arc091_c

問題

正整数N,A,Bが与えられる。
1～Nのpermutationのうち、以下を満たすものが構築可能なら構築せよ。

• LISの長さがA
• LDSの長さがB

解法

構築できない条件は以下のとおりである。

• A+B＞N+1。これは山なりに数を配置することを考えると明らか。
• A*B＜N。これは以下の構築法を考えると明らか。

まずN=A*Bのケースを考える。
これは長さBのLDSを小さい順A個くっつけることを考えるとよい。
例えばA=4,B=3だと

[3 2 1] [6 5 4] [9 8 7] [12 11 10]

N＜A*Bの場合は、A個のLDS中1個は長さBの物を残し、残りは長さ1個になるまで減らせばよい。
例えばN=9なら以下のように３つほど間引く。あとは空いた数字を詰めればよい。

[3 2 1] [6 5 *] [9 * *] [12 11 10]

このように構築するとA*B＜Nだと構築できないこともわかる。長さBのLDS A個に1個要素をどこかに入れようとすると、LDAとLISどちらかが1増えてしまう。

int N,A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	if(A+B>N+1) return _P("-1\n");
	if(1LL*A*B<N) return _P("-1\n");
	
	vector<int> T;
	int S=N-A;
	int cur=N;
	FOR(i,A) {
		int num=min(B-1,S)+1;
		S-=num-1;
		FOR(j,num) T.push_back(cur-num+1+j);
		cur-=num;
	}
	reverse(ALL(T));
	FORR(v,T) cout<<v<<" ";
	cout<<endl;
}

まとめ

方針はすぐ立ったけど、心配だったので総当たりでチェックしてたりして時間を食った。