AGC007 B - Construct Sequences

問題

[1,...,N]の順列Pがある。数列Aは単調増加、数列Bは単調減少するような数列で、 $$ A_{P_i}\ +\ B_{P_i} \lt A_{P_{i+1}}\ +\ B_{P_{i+1}} $$ を満たすような数列A, Bのペアを1つ出力せよ。

  • 2\le N\le 20000
  • p は集合 \left\{ 1,2,…,N \right\} の要素を並び替えた順列

解法

Nの制約より、巨大な数を定義して数列の添字に掛けてやると、数列の添字を"次数"や"オーダー"といったもの見立てて重み付けをすることが出来る。また、順列Pを添字とした順に単調増加させるためには、少なくとも和が1ずつずれていれば良い。

M=40010などと定義し、

  • A_i = i * M + 1 + i
  • B_i = (N - i) * M + 1

とすることで、数列の単調増加・単調減少の関係を保つことができ、かつ、和は"添字によるオーダー"がN * Mで固定になるので、和の関係はA_iの式に含まれる最後のiによってのみ影響される。

int main() {

  int N; cin >> N;
  vector<int> ps(N);
  rep(i, N) {
    cin >> ps[i]; ps[i]--;
  }

  static const int Max = 40010;

  vector<int> A(N), B(N);
  rep(i, N) {
    A[i] = B[N-1-i] = Max * i + 1;
  }

  rep(i, N) A[ps[i]] += i;

  rep(i, N) {
    cout << A[i] << " \n"[i == N-1];
  }
  rep(i, N) {
    cout << B[i] << " \n"[i == N-1];
  }
  
  return 0;
}