けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 142 C - Go To School (灰色, 300 点)

AtCoder AtCoder300点 順列を題材とした問題 ABC-C 順列テク:逆順列を考える 灰色diff そのまま覚えたい易しい教育的典型問題

この問題で要求している処理を「前処理」として要求する問題はたくさんある！！！ というわけで教育的な問題かもしれない。

問題へのリンク

問題概要

N 人の生徒がいて、出席番号 1, 2, \dots, N の生徒はそれぞれ、全体で A_i 人目に登校していることがわかっている。

これらの情報を元にして、生徒の出席番号を、登校が早い順に並び替えよ。

制約

  • 1 \le N \le 10^{5}

考えたこと

いわゆる逆順列を求める問題だね。逆順列というのは...

たとえばしたのような順列 ( 1, 2, \dots, N の並び替えのこと) が与えられたとする。

1 2 3 4 5 6 7
6 5 2 4 3 7 1

この上下の対応を保ったまま、下を 1, 2, ... の順に並び替える。

7 3 5 4 2 1 6
1 2 3 4 5 6 7

このとき、順列 (7, 3, 5, 4, 2, 1, 6) は、順列 (6, 5, 2, 4, 3, 7, 1) の逆順列であるという。

逆順列の求め方

プログラム的には順列は 0 始まりで考えた方が考えやすい。このとき順列 P_1, P_2, \dots, P_N の逆順列 Q は

for (int i = 0; i < N; ++i) Q[P[i]] = i

と簡潔に求めることができる。つまり逆順列 Q においては

  • i は P[i] 番目の要素である

ということになる。なので Q[ P[ i ] ] = i とすれば OK。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> P(N), Q(N);
    for (int i = 0; i < N; ++i) cin >> P[i], --P[i];

    for (int i = 0; i < N; ++i) Q[P[i]] = i;
    for (int i = 0; i < N; ++i) cout << Q[i]+1 << " ";
    cout << endl;
}