B - MissingNo. Editorial by MMNMM
空間計算量が小さい解法（この解説は少し発展的な解説です。この問題の標準的な解説より少し難しい表現があります。）
時間計算量を \(O(N)\) としたままワードサイズの整数を定数個だけ使うようにしても、この問題を解くことができます（\(N\) および \(A _ i\) は \(1\) ワードに収まる大きさとし、\(N\) および \(A _ i\) の値を適当な変数に入力するのに extra \(O(1)\) 空間しか必要としないとします）。
ナオヒロくんが現在持っている整数の最大値と最小値がわかれば、もともと持っていた整数が何であるかがわかります。
もともと持っていた整数と、現在持っている整数に対する何らかの値がわかれば、なくした整数が何であるかわかる場合があります。 例えば、次のような値がわかるとなくした整数が何であるかわかります。
- 和
- 積
- 積を素数 \(P(\gt A _ i)\) で割った余り
- ビット単位 XOR
ここで、特にビット単位 XOR は \(1\) ワードに収まる大きさになります。 （積を素数 \(P\) で割った余りも \(O(N)\) 時間とワードサイズの整数定数個で計算することができますが、なくした整数を特定するために追加で \(O(N)\) 時間もしくは \(O(\log P)\) 時間が必要になります。また、和も \(O(N)\) 時間とワードサイズの整数定数個で計算することができます。）
（\(1\) ワードに収まる）整数 \(L,R\ (0\leq L\leq R)\) について、\(L\) 以上 \(R\) 未満の整数全体のビット単位 XOR は定数時間で求められます。
求め方
\(L\) 以上 \(R\) 未満の整数全体のビット単位 XOR を \(f(L,R)\) で表すこととします。
\(f(L,R)=f(0,L)\operatorname{xor}f(0,R)\) が成り立ちます（ビット単位 XOR が可換で結合的であることと、\(a\operatorname{xor}a=0\) および \(0\operatorname{xor}a=a\operatorname{xor}0=a\) であることを使えば示すことができます）。
また、非負整数 \(n\) について \(f(0,4n)=0\) が成り立つことも示せます（帰納法を使い、下 \(2\) ビットとそれ以外に分けることで示すことができます）。
よって、\(f(0,L)=f(0,L)\operatorname{xor}f(0,4\lfloor L/4\rfloor)=f(4\lfloor L/4\rfloor,L)\) が成り立ちます。 これはたかだか \(3\) つの整数の xor なので、定数時間で求められます。
よって、ナオヒロくんが持っていた整数全体のビット単位 XOR は、ナオヒロくんが持っていた整数の最小値と最大値がわかれば \(O(1)\) 時間で求めることができます。
ナオヒロくんが現在持っている整数全体のビット単位 XOR は \(O(N)\) 時間と extra \(O(1)\) 空間で求められるため、これらと併せて答えを得ることができました。
実装例は以下のようになります。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N; // N を読み込む
int min_A = 1000, max_A = 0, xor_A = 0, A; // A の最小値, 最大値, 総 xor
while (N--) {
cin >> A;
min_A = min(A, min_A);
max_A = max(A, max_A);
xor_A ^= A;
}
++max_A; // 半開区間にする
while (max_A % 4 != 0)
xor_A ^= --max_A; // 全体の xor から [0, max_A + 1) の xor を除く
while (min_A % 4 != 0)
xor_A ^= --min_A; // 全体の xor から [0, min_A) の xor を除く
cout << xor_A << endl;
return 0;
}
posted:
last update: