きままにものづくり

日々の気付いたことなんかを書いてます。

SRM441Div1Easy

問題

サイズNの数列Aが与えられる。この時、もうひとつの数列Bは以下のように定義される。

  • B[0] = 0
  • B[i] = A[B[i-1]] ( i \neq 0)

Aには0~N-1までの数字が重複無く含まれている。Bに0~N-1までの数字が重複無く含まれる時の数列Pを求め、AとPの要素の位置の違いの最小値を求めよ。

解法

Bが0~N-1までの数字を含むことができない場合は、どこかにループが発生していることになる。そのループの数が答えとなる。

計算量

 O(N)

コード

広告を非表示にする