AtCoderログ：0108 - ABC 142 C

問題

問題文

高橋くんは $N$ 人の生徒たちのいるクラスの担当教師です。
生徒たちには $1$ から $N$ までの出席番号が重複なく割り当てられています。
今日は全ての生徒たちが相異なるタイミングで登校しました。
高橋くんは、出席番号 $i$ の生徒が登校した時点で、教室に $A_i$ 人の生徒たちがいたことを記録しています(出席番号 $i$ の生徒を含む)。
記録された情報を元に、生徒たちの登校した順番を復元してください。

制約

・$1 \le N \le 10^5$
・$1 \le A_i \le N$
・$A_i \ne A_j~(i \ne j)$
・入力はすべて整数

収録されている問題セット

• AtCoder Problems Boot camp for beginners Easy 100 [#016]

回答

回答1 (AC)

一番最初に生徒が登校した時の教室の人数は $1$ 人なので、それは $A_i=1$ となっている生徒です。また、二番目の生徒が登校した時の教室の人数は $2$ 人なので、それは $A_i=2$ となっている生徒です。同様に考えことで、$A_i$ が $1,2,3,...$ となるような生徒番号を出力すれば良いことがわかります。番号順に並べるにはソートを使いたくなりますが、この設問のように単純な場合には、$A_i$ をインデックスとする配列に $i$ を保存すれば良いでしょう。コードは以下のようになりました。

abc142c-1.cpp

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

int main() {
  int n;
  cin >> n;
  
  int tmp;
  vector<int> a(n+1);
  for ( int i=1; i<=n; i++ ) {
    cin >> tmp;
    a.at(tmp) = i;
  }

  for ( int i=1; i<=n; i++ ) {
    cout << a.at(i) << " ";
  }
  cout << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

$A_i$ に対してソートを適用する方針でした。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0107 - ABC 132 C
• 前の記事 → AtCoderログ：0109 - ABC 138 C