ABC171のE問題に挑戦してみた - インフラエンジニアの備忘録とか色々

初めに

レート400(茶色レート)を超えるためにになるためにAtCoder Problemsを
利用して茶色レート帯の問題を解いていまして、
今までは参加した時にしかブログを書いていなかったのですが、
書いてもまとめた方がお勉強になるので参加していない時も
たまに書こうかと思います。(今週はABCありませんし)

https://kenkoooo.com/atcoder/#/table/

制限時間を決めて解いているんですが、時間内に解き終わらなかったので、
主に解説を見て「なるほどなぁ」となったところについて書いて行きます。

https://atcoder.jp/contests/abc171

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

E - Red Scarf

N匹の猫がおり、それぞれの猫は整数が記載された赤いスカーフを付けています。
$A_1～A_N$ までの入力が与えられ、 $A_i$ はi番目の猫のスカーフに記載されている整数を除いた
猫のスカーフに記載された整数をXORした結果となります。
この情報を元にそれぞれの猫のスカーフに記載されている整数を求めます。

解説を見てからの回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;
int main(){

ll N;
ll sum = 0;

cin >> N;

vector<ll> a(N);

// 入力とA1～ANの値のXORした結果を格納
for(ll i = 0;i < N;++i){
    cin >> a[i];
    sum ^= a[i];
}

// 元の値を求る
for(ll i = 0;i < N;++i) a[i] ^= sum;

// 結果を出力
for(ll i = 0;i < N;++i) cout << a[i] << endl;

return 0;

}

※下記に表示しているイメージは0起算で書いてます。

まずは、テストケースのパターンを元に考えてみましょう。
$X_i$ をi番目の猫のスカーフに記載されている整数とすると、
$A_1 ～ A_N$ を以下のような形で表す事が出来ます。