Codeforces #502 (Div. 1 + Div. 2) C. (R1600)

LIS and LDS のバリエーション。

問題へのリンク

問題概要

1〜N の各順列について

• LIS (最長増加部分列) の長さが A
• LDS (最長減少部分列) の長さが B

とする。A + B を最小化し、A + B が最小となるような順列を具体的に 1 つ求めよ。

制約

• 1 <= N <= 10⁵

考えたこと

LIS and LDS と呼ばれる超有名問題で、

• A + B <= N+1
• AB >= N

が成立することが、そのような順列が存在するための必要十分条件である。 AB >= N より、A + B >= 2|√N| (ガウス記号) が成立していることはわかる。

• N が平方数なら、A = B = √N
• そうでないなら、
  • もし A = |√N|, B = |√N| + 1 として AB >= N になるならそれで OK
  • そうならないなら A = |√N| + 1, B = |√N| + 1 とすれば OK

#include <iostream>
#include <vector>
using namespace std;


// LIS and LDS
// A + B <= N+1, AB >= N are necessarily and sufficient
vector<long long> solve(long long N, long long A, long long B) {
    vector<long long> res;
    for (long long i = B-1; i >= 0; --i) res.push_back(i);
    
    if (A == 1) return res;
    
    long long rem = N - B;
    long long p = rem / (A-1);
    long long r = rem % (A-1);
    
    long long b = r;
    long long c = A-1-r;
    
    for (int i = 0; i < b; ++i) {
        int size = (int)res.size();
        for (int j = 0; j < p+1; ++j) {
            res.push_back(size + p - j);
        }
    }
    for (int i = 0; i < c; ++i) {
        int size = (int)res.size();
        for (int j = 0; j < p; ++j) {
            res.push_back(size + p-1 - j);
        }
    }
    
    return res;
}

int main() {
    long long n;
    while (cin >> n) {
        long long sq = 1;
        while ((sq + 1) * (sq + 1) <= n) ++sq;
        long long a, b;
        vector<long long> res;
        if (sq * sq == n) {
            a = sq, b = sq;
            res = solve(n, a, b);
        }
        else {
            if (sq*(sq+1) >= n) a = sq, b = sq+1;
            else a = sq+1, b = sq+1;
            res = solve(n, a, b);
        }
        
        for (int i = 0; i < res.size(); ++i) {
            cout << res[i]+1;
            if (i != (int)res.size()-1) cout << " ";
        }
        cout << endl;
    }
}