ARC091 E : LISDL(700)
作成日：2018.03.14
最終更新日：2018.03.14
問題概要
$1$から$N$までの整数からなる順列で、最長増加部分列(LIS)の長さが$A$、最長減少部分列(LDS)の長さが$B$であるものが存在するか判定せよ。
また存在する場合は、そのうちの一つを構成せよ。
制約
$1 \leq N,A,B \leq 3 \times 10^5$
考え方
まずは数列が与えられた時にLIS及びLDSの長さを求めることを考える。
先頭から$i$個見た時にその数を含むLIS,LDSの長さをそれぞれ$a_i$,$b_i$とすると、$A = max(A_i)$,$B = max(B_i)$となる。
この時$a_1$$= b_1$$= 1$であり、$j \lt i$を満たすある$j$において$a_i = a_j + 1$,$b_i = b_j$または$a_i = a_j$,$b_i = b_j + 1$である。
よって$a_i + j_i$の増加量は高々$1$であるから、$A + B$$\leq 2 + (N - 1)$$= N + 1$である。
また$1 \leq a_i \leq A$,$1 \leq b_i \leq B$であり、$i \gt j$かつ$a_i = a_j$かつ$b_i = b_j$とすると数列の要素はいずれも異なることからLISまたはLDSのいずれかを大きくすることができるので矛盾する。
このことから$N \leq AB$が分かる。
以上より$A+B-1$$\leq N$$\leq AB$である必要がある。
$N = AB$を達成するために$(a_i,b_i)$の組をすべて作ることを考える。
規則正しく並べた$(1,1)$,$(1,2)$,$...$,$(1,B)$,$(2,1)$,$(2,2)$,$...$,$(A,B)$は$a_i$,$b_i$の条件に反しない。
またこれを$a_i$が等しいものをまとめてみると、前のまとまりにある要素よりも後のまとまりにある要素の方が大きい必要があることが分かる。
さらに、まとまりの中では要素の値が単調減少していることも分かる。
よって$B,B-1,$$...,$$2,1,2B,2B-1,$$...,$$AB-A+1,$$AB-A$と並べれば、$N = AB$を達成できる。
ここから不要な数を抜き出して詰めれば、他の場合も構成することができる。
ソースコード
マクロ等はこちら
int N,A,B;
int main(){
cin >> N >> A >> B;
if(A+B-1>N || (LL)A*B<(LL)N){
cout << -1 << endl;
} else {
int x = N - A;
int m = 0;
while(m<N){
int y = 0;
if(x>=B-1){
y = B;
} else {
y = x+1;
}
repm(i,m+y,m) cout << i << ' ';
m += y;
x -= y-1;
}
cout << endl;
}
return 0;
}解法まとめ
$A+B-1 \leq N \leq AB$の時に条件を満たす順列が存在し、そうでない時は存在しない。(5,6行)
構成は以下のように行えば良い。
$1$から$N$まで順に並べた数列を、各グループが$B$個以下となるように$A$個のグループを先頭から順に整数をとっていくことで作る。
但しグループのうちの1つは必ず$B$個の要素を含むようにする。
グループ内の整数の最大値が小さいものから順に、グループ内では降順になるように並べる。(8-21行)