第二回 アルゴリズム実技検定 E - 順列 解説

問題

問題文は本家サイトにあります：第二回 アルゴリズム実技検定 E - 順列

問題概要

$1,2,\cdots,N$ の順列 $A_1,A_2,\cdots,A_N$ が与えられるので、各整数 $i\ (1\leqq i \leqq N)$ に対して次の条件を満たす最小の正整数 $j$ を答えなさい。

条件： $x=i$ とする。 $x$ を $A_x$ で置き換えるという操作を $j$ 回行った後、 $x=i$ となる。

制約

$1\leqq N \leqq 100$

解説

リンク先の入力例にもありますが、1 3 2 5 6 4 の例を考えてみます。

$i=1$ の場合は次のようになります。まず、 $x=1$ です。 $x$ を $A_x$ で置き換えるのですが、これは $x$ を $A_1$ で置き換える、つまり、 $1$ に置き換えるということなので、置き換えた後は $x=1$ のままです。 $x=i$ だから、このときの $j$ は $1$ です。

$i=3$ の場合は次のようになります。まず、 $x=3$ です。 $x$ を $A_x$ で置き換えるのですが、これは $x$ を $A_3$ で置き換える、つまり、 $2$ に置き換えるということなので、置き換えた後は $x=2$ です。次に、 $x$ を $A_2$ で置き換える、つまり、 $3$ に置き換えるということなので、置き換えた後は $x=3$ となります。2回目で $x=i$ となるので、このときの $j$ は $2$ です。

$i=5$ の場合は次のようになります。まず、 $x=5$ です。 $x$ を $A_x$ で置き換えるのですが、これは $x$ を $A_5$ で置き換える、つまり、 $6$ に置き換えるということなので、置き換えた後は $x=6$ です。次に、 $x$ を $A_6$ で置き換える、つまり、 $4$ に置き換えるということなので、置き換えた後は $x=4$ となります。 $A_4=5$ なので、もう一度置き換えると $x=5$ となります。3回目で $x=i$ となるので、このときの $j$ は $3$ です。

これは、最悪でも100回繰り返せば元に戻ってくるはずなので、それぞれの $i$ に対して実際に試してみると答えが得られます。C++で書けば、次のようになります。（下のコードでは、 $0$ から $N-1$ までの順列に置き換えて考えています）

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

int main() {

  int N; cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i]; A[i]--;
  }

  for (int i = 0; i < N; i++) {
    int x = i, ans = 0;
    while (true) {
      ans++;
      x = A[x];
      if (x == i) {
        cout << ans << ' ';
        break;
      }
    }
  }
  return 0;
}