【AtCoder】ABC 461 B - The Honest Woodcutters

B - The Honest Woodcutters

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 34 / NoviSteps: 7Q / 配点: 200 点

問題概要

$N$ 人の木こりが斧を $1$ 個ずつ持っていたが、全員が斧を池に落としてしまった。

池には $N$ 個の斧 $1,2,\dots,N$ が沈んでおり、各木こり $i$ は「自分が持っていた斧は斧 $A_i$ である」と主張している。 一方、この池の女神は、各斧 $i$ を持っていたのは木こり $B_i$ であることを知っている。

$N$ 人の木こり全員が本当のことを言っているかどうかを判定せよ。

制約

• $1 \leq N \leq 100$
• $1 \leq A_i \leq N$
• $1 \leq B_i \leq N$
• $A_i \neq A_j\;(i \neq j)$
• $B_i \neq B_j\;(i \neq j)$
• 入力される値はすべて整数

考察

「木こり $i$ が本当のことを言っている」という条件を言い換えると、 $B_{A_i} = i$ となる。

したがって、全ての $i$ について $B_{A_i} = i$ が成り立つかどうかを判定すればよい。

実装例

実装時はインデックスのずれに注意すること。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N;
11.    cin >> N;
12.    vector<int> A(N), B(N);
13.    rep(i, 0, N) cin >> A[i];
14.    rep(i, 0, N) cin >> B[i];
15. 
16.    rep(i, 0, N) {
17.        if (B[A[i] - 1] != i + 1) {
18.            cout << "No" << endl;
19.            return 0;
20.        }
21.    }
22. 
23.    cout << "Yes" << endl;
24.    return 0;
25.}

Submission #76434172 - AtCoder Beginner Contest 461

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実装時間: 5 分以内

コメント

特に言うことは無し。