[AGC064] A - i i's

[Q] https://atcoder.jp/contests/agc064/tasks/agc064_a

考察
・しれっとあるけど、先頭と末尾の要素も条件の対象。見落としそう。
1 <= |A[L] - A[1]| <= 2
・N=4のサンプルを活用しようと思う。

N=4
1 3 4 2 4 3 4 2 4 3

N=5は？
N=4にプラス1してみる。
2 4 5 3 5 4 5 3 5 4
ここに足りない値は、1,2,3,4,5。
これをいい感じに配置する。

A. (1) 2 4 5 3 5 4 5 3 5 4 (5 4 3 2)
1. 先頭に1を配置。
2. 末尾に下降系になるように、5 4 3 2をいい感じに配置。

N=6は？
N=5にプラス1してみる。
2 3 5 6 4 6 5 6 4 6 5 6 5 4 3
ここに足りない値は、1,2,3,4,5,6。いい感じに配置する。

A. (1) 2 3 5 6 4 6 5 6 4 6 5 6 5 4 3 (5 6 4 3 2)

O(N^3)だけどなんか間に合った。

実装

int main() {
  cincout();
  ll N;
  cin >> N;
 
  if (N == 3){
    cout << "1 3 2 3 2 3" << endl;
    return 0;
  }
  if (N == 4){
    cout << "1 3 4 2 4 3 4 2 4 3" << endl;
    return 0;
  }

  // N = 4 の形から、N = 5,6,...と広げていく。
  vector<ll> A = {1, 3, 4, 2, 4, 3, 4, 2, 4, 3};
  for(ll i = 5; i <= N; ++i){
    // 1,2,3,4,5が1個ずつ足りないはず。
    vector<ll> B;
    B.emplace_back(1); // 先頭に1
    rep(a, A.size()){
      B.emplace_back(A[a] + 1);
    }
    bool used[i + 1]{};
    // 上昇系
    ll a = B.back();
    while (a < i){
      ll na = min(i, a + 2);
      used[na] = true;
      B.emplace_back(na);
      a = na;
    }
    // 下降系
    for(; a >= 2; --a){
      if (used[a]) continue;
      B.emplace_back(a);
    }
    swap(A, B);
    auto debug=[&](){
      cerr << i << ": ";
      for(auto a : A) cerr << a << " ";
      cerr << endl;
    };
    // debug();
  }
  rep(i, A.size()) cout << A[i] << " \n"[i == A.size() - 1];
}

https://atcoder.jp/contests/agc064/submissions/44562255