[AtCoder] ABC 171 E – Red Scarf
問題
方針
排他的論理和 xor を \( \oplus \) で表現します。\( i \) 番目のスカーフの番号を \( b_i \) とすると、
\[ a_i = b_1 \oplus b_2 \oplus \cdots \oplus b_{i-1} \oplus a_{i+1} \oplus \cdots \oplus b_{N}\]
ここで、\( a_i \) の排他的論理和を考えます。
\begin{eqnarray}
a_1 \oplus \cdots \oplus a_{N} &=& (b_1 \oplus \cdots \oplus b_1) \oplus \cdots \oplus(b_N \oplus \cdots \oplus b_N)\\
&=& b_1 \oplus \cdots \oplus b_N
\end{eqnarray}
となります。これは、\( b_i \oplus b_i = 0 \) と \( b_i \oplus 0 = b_i \) と \( N \) が偶数であることを利用して導けます。
また、
\begin{eqnarray}
a_1 \oplus \cdots \oplus a_{N}\oplus a_1 &=& b_1 \oplus \cdots \oplus b_N \oplus (b_2 \oplus \cdots \oplus b_N)\\
&=& b_1
\end{eqnarray}
となるので、任意の \( b_i \) について求めることができます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N; cin >> N; ll a[N]; ll t = 0; for (int i = 0; i < N; i++) { cin >> a[i]; t = (t ^ a[i]); } for (int i = 0; i < N; i++) { if (i == N - 1) { cout << (t ^ a[i]) << "\n"; } else { cout << (t ^ a[i]) << " "; } } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません