Red and Blue

2 secs 1024 MB

この問題では主にソートか連想配列を問います。

$2$ つの列 $R,B$ が等しくなるのは、 $R,B$ にある要素の個数が両方とも等しくなる場合のみです。このように言うと連想配列で各要素の個数を確認する解法に他ないと思われますが、実は $R,B$ を昇順か降順にソートし、 $1$ 要素ずつ確かめていくことでも判定することが可能です。例えば $R=(1,2,3,4,4),B=(5,2,4,1,3)$ の場合などでは、 $R,B$ を順列として一致することは $R,B$ を両方とも昇順または降順にソートをしたものが一致することが必要十分です。よって $R,B$ をソートする時間がネックとなり、 $O(N \log_{}N)$ で実装することが可能です。連想配列の解法でも同じような計算量になります。

以下はソートを用いた解答例(C++)です。

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,a,b) for(int i = a; i < b; i++)
#define all(A) (A).begin(),(A).end()
#define MOD 998244353
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
ll INF = 1LL<<60;
struct Edge { int to; int cost; int from; };
using Graph = vector<vector<int>>;
​
int main(void){
    int n; cin >> n;
    vector<int> A(n),B(n);
    rep(i,n) cin >> A[i];
    rep(i,n) cin >> B[i];
​
    sort(all(A)); sort(all(B));
    cout << (A == B ? "Yes" : "No");
}