ABC171E XORの計算がわからない

Question

ABC171の問題EでXORの計算がわからない

ABC171_Eで以下のように考えました。

サンプル１の場合）
N=4
(^はXOR)
x2^x3^x4=20　…①
x1^x3^x4=11　…②
x1^x2^x4=9　 …③
x1^x2^x3=24　…④

①^②を考えると
x1^x2=20^11=32
他も同様にすると
x1^x2=31　…⑤
x2^x3=2　 …⑥
x3^x4=17　…⑦
x4^x1=24 …⑧

この式をもとに
x1を１から1000000000まで増やしていき、x1が決まればx2が決まりx2が決まればx3が決まるのでこれを繰り返し、⑤⑧までを満たすx1x4を探すという方法を考えました。

ソースコード

#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[i];

  vector<int> x(N);

  int num1,num2;
  vector<int> XOR_num(N);
  for(int i=0;i<N;i++){
    if(i==N-1){
      num1=a[0];
      num2=a[N-1];
    }else{
      num1=a[i];
      num2=a[i+1];
    }

    XOR_num[i]=num1^num2;
  }

  for(int num=1;num<=1000000000;num++){
    //x[0]がnumのとき
    x[0]=num;
    for(int i=0;i<=N-2;i++){
      x[i+1]=x[i]^XOR_num[i];
    }
    if((x[0]^x[N-1])==XOR_num[N-1]){
      break;
    }
  }

  for(int i=0;i<N;i++){
    cout << x[i] << endl;
  }
}

発生している問題

サンプルの入力が以下です。
4
20 11 9 24

これを実行すると
x1=1
x2=30
x3=28
x4=13
になりました。

これは①〜④までの式は満たしませんでした。

###試したこと
サンプルのx1の解を固定して実行したところx2~x4も正しく出力されました。

###わからないこと
式⑤⑧で求めた解が式①④を満たさなくなってしまうのはなぜなのでしょうか？

Comments

[YT0014]

①から④ならば、⑤から⑧は真ですが、逆は必ずしも真ならずです。
⑤から⑧の式をどう組み合わせても、①が導けないので、逆は偽とみなすべきです。
私ならば、x1=②^③^④を利用します。Nが偶数と奇数で変わりますが。

[kyokio]

なるほど！
わかりやすい解説ありがとうございます。

Answer 1

とりあえず、「探すのはめっちゃ効率悪い。考え直そうよ」ってのは置いといて、
・探してるループの中のfor()の継続条件は i<N-1 ですよね？
で、その下のループから抜ける判断の中身を

break;

から

printf("%d? yes!\n", num);  // breakせず続けまくる

に書き換えて動かしてみましょう。ちょっとびっくりするかもしれません。

最初の回答は遠回しだったので、コードの動きに合わせて書き直します。
ループの1回目で
x2 = num ^ 値(5) としたので、ループの2回目では
x3 = x2 ^ 値(6) = (num ^ 値(5)) ^ 値(6)、同様の3回目
x4 = x3 ^ 値(7) = ((num ^ 値(5)) ^ 値(6)) ^ 値(7)
x1 = x4 ^ 値(8) = (((num ^ 値(5)) ^ 値(6)) ^ 値(7)) ^ 値(8)
= num ^ x1^x2 ^ x2^x3 ^ x3^x4 ^ x4^x1 = num
つまり、numに何を入れても結果はnumで、「見つかったつもり」の条件が真になります。
（ってことを最初の追記・修正依頼のひと（YT0014さん）も言ってたのか…）

2番目の回答のやり方で行きましょう。

Answer 2

式⑤⑧で求めた解が式①④を満たさなくなってしまうのはなぜなのでしょうか？

この質問にはすぐには答えられませんが、私なら次のようなコードを書きます。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n, m = 0;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i], m ^= a[i];
	cout << (m ^ a[0]);
	for (int i = 1; i < n; i++) cout << ' ' << (m ^ a[i]);
	cout << endl;
}

Answer 3

全く間違っているそうです。すみません

(5)(8)を「すべて」満たしていれば当然(1)(4)を満たします

しかし、実行結果

x1=1

x2=30
x3=28
x4=13

は x4^x1 = 13^1 = 12 なので(8)を満たしていないです

breakの判定あたりが怪しい気がします。取り急ぎ。