Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What are the problem?
@RoadLynton

AtCoderログ:0046 - ARC 124 B

問題

問題文

非負整数のみからなる長さ $N$ の数列 $a,b$ が与えられます。$a,b$ の
$i$ 番目の要素はそれぞれ $a_i,b_i$ です。
非負整数 $x$ が以下の条件を満たすとき、$x$ を よい数 と呼びます。
・条件:$b$ を並べ替えて、$1 \le i \le N$ を満たすどの整数 $i$ についても $a_i~{\rm XOR}~b_i=x$ が成立するようにすることができる。ここで、
XOR はビットごとの排他的論理和である。
よい数を小さい方からすべて列挙してください。

制約

・与えられる入力は全て整数
・$1 \le N \le 2000$
・$0 \le a_i, b_i < 2^{30}$

回答

回答1 (AC)

数列 $b$ の要素数は $N \le 2000$ なので、数列 $b$ の並び替えた全ての数列を列挙するのは無理です。また、$0 \le a_i, b_i < 2^{30}$ より $0 \le x \le 2^{30}$ となり、$x$ の全数探索も無理です。

そもそも よい数 $x$ はどのような条件を満たすでしょうか。$x$ が よい数 であるとき、ある $i$ に対して $a_i~{\rm XOR}~b_j = x$ となる $j$ が存在します。とくに $i=1$ とおけば $a_1~{\rm XOR}~b_j = x$ となる $j$ が存在することが必要です。したがって、よい数 $x$ は $N$ 個の値 $a_1~{\rm XOR}~b_1,~a_1~{\rm XOR}~b_2,~a_1~{\rm XOR}~b_3,~\ldots, a_1~{\rm XOR}~b_N$ に含まれているはずです。逆に、この $N$ 個の値以外に よい数 は考えられません。 つまりこの $N$ 個の数は 良い数 の候補として扱うことが出来るのです。

$a_i~{\rm XOR}~b_i=x$ の両辺に $b_i$ を XOR すると
$$
a_i~{\rm XOR}~b_i~{\rm XOR}~b_i=x~{\rm XOR}~b_i
$$
となりますが、任意の値 $z$ に対して $z~{\rm XOR}~z=0$ となるので
この式は
$$
a_i=x~{\rm XOR}~b_i
$$
と等価です。そこで、上記のそれぞれの候補 $x$ に対して $c_i=x~{\rm XOR}~b_i$ を計算し、数列 $c$ と $b$ が一致するかを調べれば良いでしょう。

以上の手順をコードにすると以下のようになりました。なお、C++ では XOR 演算は ^ で表します。

arc124b-1.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i);
  }
  sort( a.begin(), a.end() );

  vector<int> b(n), xcandidate(n);
  for ( int i=0; i<n; i++ ) {
    cin >> b.at(i);
    xcandidate.at(i) = a.at(0)^b.at(i);
  }

  set<int> x;
  vector<int> c(n);
  for( int i=0; i<n; i++ ) {
    for ( int j=0; j<n; j++ ) {
      c.at(j) = xcandidate.at(i)^b.at(j);
    }
    sort( c.begin(), c.end() );

    bool is_equal = true;
    for ( int k=0; k<n; k++ ) {
      if ( a.at(k)!=c.at(k) ) {
        is_equal = false;
      }
    }

    if ( is_equal ) {
      x.insert(xcandidate.at(i));
    }
  }

  cout << (int)x.size() << endl;
  for( auto xx : x ) {
    cout << xx << endl;
  }
}

$N$ 個の候補数のそれぞれに対して $N$ この要素からなる数列 $c$ を計算・ソートするので、全体の計算量は $O(N) \times O(N \log{N})=O(N^2 \log{N})$ となります。

調べたこと

AtCoder の解説公式解説

回答1と同じ方針でした。

リンク

前後の記事

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
0
Help us understand the problem. What are the problem?