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と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0045 - ABC 083 B