ABC461 B - 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}

$0$ 番の斧を見る。
b[0] は $1$ なので、本当の所有者は $1$ 番の人である。
その人は、a[1] は $0$ つまり $0$ 番の斧を持っていると主張しているので正しい。

$1$ 番の斧を見る。
b[1] は $2$ なので、本当の所有者は $2$ 番の人である。
その人は、a[2] は $1$ つまり $1$ 番の斧を持っていると主張しているので正しい。

$2$ 番の斧を見る。
b[2] は $0$ なので、本当の所有者は $0$ 番の人である。
その人は、a[0] は $2$ つまり $2$ 番の斧を持っていると主張しているので正しい。

全ての斧について矛盾がないので、Yes を出力する。

特になし。

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