mayoko’s diary

プロコンとかいろいろ。

CodeChef Longest Increasing Subsequences

問題

Contest Page | CodeChef

1, 2, ..., N の順列を使って, LIS が K 個あるようなものを作れ。ただし, 1 <= N <= 100

解法

とりあえずチェックプログラムを作っておくほうが良さそうなので, まずそっちを作りましょう(下のプログラムで check ってやつ)。

LIS の個数を求めるアルゴリズムには O(N log N) のものがあるらしいですが, 今回そんな高性能なアルゴリズムを作る必要はないので, O(N^3) を作ります。

dp[i][k] = (i 番目までで LIS の長さが k であるようなものの場合の数) とします。すると, LIS の個数は dp[*][maxK] の和で求められます。また, dp の遷移は

dp[i][k] = sum(dp[j][k-1]) (ただし j は j < i, v[j] < v[i] を満たす)

です。これでチェックプログラムはできました。後は解法を考えます。

いろんな解き方がありそうな気がしますが, 僕は以下のようにして解きました。イメージは下図にあげておきます。
f:id:mayokoex:20160607180825j:plain
長さ 6 の LIS をたくさん作ることを考えます。方針としては, x+8, x+7, ..., x+1 と並んだものをまず小さい順に 6 個用意しておきます。すると, 例えば 68, 67, ..., 61 の直前にあるところでは長さ 1 の LIS を作っておけば(この要素を y とする), 自然に y -> (68 ~ 61) -> (76 ~ 69) -> ... -> (100 ~ 93) といった具合にして, (y としてあり得る数の個数) * 8^6 個の場合の数を稼ぐことができます。

このようにして長さ 2, ..., 長さ 5 の LIS の数を調整することで, 8 進数的に数を増やしていくことができるので, 与えられた K に対して必ず何らかの数列を構成することができます。

後は 長さ i+1 の LIS を構成できれば良いのですが, これは上の写真の下のほうに書いてあるように,

  • 後半 i 個は x, x+1, ..., x+i-1 のように素直に並べる
  • 前半は x, x-1, ... のようにすることによって LIS の流れを作る

とやれば良いです。

このように適当に並べても, 100 個以内なら間に合います(最初考えていたのは 10 でしたが, 10 だとここまで適当では間に合いません)。

const int MAXN = 111;
int dp[MAXN][MAXN];
int check(const vi& ans) {
    int n = ans.size();
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) {
        dp[i][1] = 1;
        for (int j = 0; j < i; j++) if (ans[i] > ans[j]) {
            for (int k = 1; k <= j+1; k++) if (dp[j][k]) {
                dp[i][k+1] += dp[j][k];
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int k = 7; k <= i; k++) {
            if (dp[i][k] > 0) return -1;
        }
        cnt += dp[i][6];
    }
    return cnt;
}

void print(const vi& v) {
    int sz = v.size();
    cout << sz << endl;
    for (int i = 0; i < sz; i++) {
        cout << v[i] << (i < sz-1 ? " " : "");
    }
    cout << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int K;
        cin >> K;
        vi ans;
        int now = 60;
        int insert = 68;
        int p8 = 1<<(3*5);
        for (int i = 0; i < 6; i++) {
            int k = K/p8;
            k %= 8;
            p8 /= 8;
            for (int j = 0; j < k; j++)
                ans.push_back(now-i-j);
            for (int j = 0; j < i; j++)
                ans.push_back(now-i+j+1);
            now = now-i-k;
            if (i < 5) {
                for (int j = 0; j < 8; j++)
                    ans.push_back(insert-j);
                insert += 8;
            }
        }
        int sz = ans.size();
        vector<int> v(ans.size());
        for (int i = 0; i < sz; i++)
            v[i] = ans[i];
        sort(v.begin(), v.end());
        for (int i = 0; i < sz; i++)
            ans[i] = lower_bound(v.begin(), v.end(), ans[i]) - v.begin() + 1;
        print(ans);
        //cout << check(ans) << endl;
    }
    return 0;
}