AtCoderログ：0105 - ABC 217 C

問題

問題文

$1,2,…,N$ が $1$ 回ずつ現れる長さ $N$ の数列を「長さ $N$ の順列」と呼びます。
長さ $N$ の順列 $P=(p_1,p_2,\ldots,p_N)$ が与えられるので、以下の条件を満たす長さ $N$ の順列 $Q=(q_1,\ldots,q_N)$ を出力してください。
・全ての $i (1 \le i \le N)$ に対して $Q$ の $p_i$ 番目の要素が $i$ である。
ただし、条件を満たす $Q$ は必ずただ $1$ つ存在することが証明できます。

制約

・$1 \le N \le 2 \times 10^5$
・$(p_1,p_2,\ldots,p_N)$ は長さ $N$ の順列である。
・入力は全て整数である。

回答

回答1 (AC)

例を使って設問の意味を考えます。$N=3$ として $P=(3,1,2)$ という順列を考えると、これは $1$ を $3$ に、$2$ を $1$ に、$3$ を $2$ に置き換えるという意味で、$1 \to 3$, $2 \to 1$, $3 \to 2$ と表すことが出来ます。順列 $Q=(q_1,q_2,q_3)$ は置き換えた結果が $1,2,3$ になるので、
さきほどのルールの順番を入れ替えて $2 \to 1$, $3 \to 2$, $1 \to 3$ にすれば良いので、$Q=(2,3,1)$ となることがわかります。したがって、インデックスが $i$ のときに $p_i$ を読み込んだとすると、$q_{p_i}=i$ になる、つまりインデックス $p_i$ の値が $i$ になることがわかります。コードは以下のようになりました。

abc217c-1.cpp

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

int main() {
  int n;
  cin >> n;

  vector<int> p(n);
  int t;
  for ( int i=0; i<n; i++ ) {
    cin >> t;
    p.at(t-1) = i;
  }

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

調べたこと

AtCoder の解説 → 公式解説

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

リンク

前後の記事

• 前の記事 → AtCoderログ：0104 - ABC 217 B
• 次の記事 → AtCoderログ：0106 - ABC 161 C