AGC007 B - Construct Sequences

問題

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

• 
• は集合 の要素を並び替えた順列

解法

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

などと定義し、

• 
• 

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

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;
}