ARC091 E : LISDL(700)
作成日：2018.03.14
最終更新日：2018.03.14
問題概要
11からNNまでの整数からなる順列で、最長増加部分列(LIS)の長さがAA、最長減少部分列(LDS)の長さがBBであるものが存在するか判定せよ。
また存在する場合は、そのうちの一つを構成せよ。
制約
1≤N,A,B≤3×1051≤N,A,B≤3×105
考え方
まずは数列が与えられた時にLIS及びLDSの長さを求めることを考える。
先頭からii個見た時にその数を含むLIS,LDSの長さをそれぞれaiai,bibiとすると、A=max(Ai)A=max(Ai),B=max(Bi)B=max(Bi)となる。
この時a1=b1=1であり、j<iを満たすあるjにおいてai=aj+1,bi=bjまたはai=aj,bi=bj+1である。
よってai+jiの増加量は高々1であるから、A+B≤2+(N−1)=N+1である。
また1≤ai≤A,1≤bi≤Bであり、i>jかつai=ajかつbi=bjとすると数列の要素はいずれも異なることからLISまたはLDSのいずれかを大きくすることができるので矛盾する。
このことからN≤ABが分かる。
以上よりA+B−1≤N≤ABである必要がある。
N=ABを達成するために(ai,bi)の組をすべて作ることを考える。
規則正しく並べた(1,1),(1,2),...,(1,B),(2,1),(2,2),...,(A,B)はai,biの条件に反しない。
またこれをaiが等しいものをまとめてみると、前のまとまりにある要素よりも後のまとまりにある要素の方が大きい必要があることが分かる。
さらに、まとまりの中では要素の値が単調減少していることも分かる。
よって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≤N≤ABの時に条件を満たす順列が存在し、そうでない時は存在しない。(5,6行)
構成は以下のように行えば良い。
1からNまで順に並べた数列を、各グループがB個以下となるようにA個のグループを先頭から順に整数をとっていくことで作る。
但しグループのうちの1つは必ずB個の要素を含むようにする。
グループ内の整数の最大値が小さいものから順に、グループ内では降順になるように並べる。(8-21行)