ABC461B - The Honest Woodcutters

解法

0-indexed と 1-indexed が入り混じると面倒なので、最初に全て 0-indexed に統一するとよい。

女神視点で、各斧について、本当の所有者が名乗りを上げているかをチェックしていく。

i 番の斧の所有者は、b[i] 番の人である。
b[i] 番の人は、a[b[i]] 番の斧を持っていると主張している。
つまり、a[b[i]] の値が i そのものであれば、嘘は生じていない。

全員が正直かを確認するには、最初に "Yes" で初期化された文字列を用意するとよい。
嘘が $1$ 回でも見つかった時点で、それを "No" に書き換える。

C問題以降の知識になるが、$2$ つのデータ a と b が、以下の関係になっていることを「逆写像」という。

配列の中から値を探すことを何度も繰り返す場合、最初に逆写像を用意すると高速化できる。
今後のために覚えておきたい。

入力を受け取り、全て 0-indexed にしておく。

n: 3
a: {2, 0, 1}
b: {1, 2, 0}

出力用変数を用意しておく。

result: "Yes"

$0$ 番の斧をチェックする。
b[0] を見ると 1 であり、a[1] を見ると 0 である。
この部分は逆写像として正しいので、出力用変数には何もしない。

$1$ 番の斧をチェックする。
b[1] を見ると 2 であり、a[2] を見ると 1 である。
この部分は逆写像として正しいので、出力用変数には何もしない。

$2$ 番の斧をチェックする。
b[2] を見ると 0 であり、a[0] を見ると 2 である。
この部分は逆写像として正しいので、出力用変数には何もしない。

最終的な出力用変数の中身が答え。

result: "Yes"

特になし。

木こり視点でチェックしてもよい。
その場合、b[a[i]] が i であるか確認することになる。