CodeChef SnackDown Online Pre-elimination round A - Longest Increasing Subsequences

問題

100 以下の自然数を使ってLISがちょうどK個存在する数列を作れ。同じ数字は1度しか使えない。

解法

{ 2 1 4 3 }で 2*2 通りのLISが含まれる数列を作れる。ここの左側に {5 6} をつけると{5 6} {2 1 4 3}となり 1通り増えて 2^2+1 通りになる。さらに右側に8 7 をつけると、{5 6} {2 1 4 3 8 7} で (2^2 + 1)*2 通りとなる。
つまりどんな自然数でも、2進数表記にして以下の手順を実行することで数列を作る事ができる。

（ここに以下の手順を書く予定だったが挫折した）

コード

#include <bits/stdc++.h>
using namespace std;

vector<int> solve(int K) {
  if (K == 1) return {1};

  vector<int> v;
  while (K) {
    v.push_back(K % 2);
    K /= 2;
  }
  int n = v.size();
  vector<int> left, right;
  right.push_back(2);
  right.push_back(1);
  int cur = 3;

// K を2進数表記にしたものを前の桁から見ていく
  for (int i = n - 2; i >= 0; --i) {
// i 桁目が1ならば、右側と同じ長さのLISが出来るまで数字を追加する(LISが1増える)
    if (v[i] == 1)
      while (left.size() < right.size() / 2) left.push_back(cur++);

// 2つ数字を入れるとLISが 2倍になる
    if (i > 0) {
      right.push_back(cur + 1);
      right.push_back(cur);
      cur += 2;
    }
  }

  left.insert(left.end(), right.begin(), right.end());
  return left;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    int K;
    cin >> K;
    vector<int> ans = solve(K);
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); ++i) {
      if (i > 0) cout << ' ';
      cout << ans[i];
    }
    cout << '\n';
  }
}