BOJ 10736 - XOR삼형제 2
Claim 1. 정답이 되는 가장 긴 수열 중 하나는 연속된 수들의 집합이다.
따라서 정답이 되는 수열 $A$가 $A=[x,x+1,x+2,x+3,\dots]$ 이다.
$x$의 후보를 생각해본다.
$\vert A \vert=k$ 라면 $x \sim x+k-1$ 까지의 어떤 세 수는 $\oplus$이 $0$이 아니여야 한다.
Lemma 1. $x=2^y$ 라면 항상 $[2^y, 2^y + 2^{y+1})$ 범위의 수들을 포함할 수 있다.
$2^y \oplus 2^{y+1} \oplus 2^y+2^{y+1}=0$ 이기 때문에 최대 범위는 $2^y+2^{y+1}-1$ 이다.
$[2^y,2^y+2^{y+1})$ 에 존재하는 서로 다른 세 수 $\alpha, \beta, \gamma$ 를 고려한다.
$\alpha \oplus \beta \not\in [2^y, 2^y+2^{y+1})$ 임을 보이면 된다.
$wlog. \alpha < \beta$ 이라 하자.
$\alpha < \beta < 2^{y+1}$ $\rightarrow$ $\alpha \oplus \beta$의 가장 큰 bit는 최대 $2^{y-1}$ 이기 때문에 옳다.
$\alpha < 2^{y+1} \le \beta$ $\rightarrow$ $\alpha \oplus\beta$ 는 $2^y,~2^{y+1}$ bit가 $1$이고 이런 수는 범위내에 없다.
$2^{y+1} \le \alpha < \beta$ $\to$ $\alpha \oplus \beta$의 가장 큰 bit는 최대 $2^{y-1}$ 이기 때문에 옳다. $\square$
Claim 2. Claim 1이 참이라면, 항상 $x=2^y$ 이다.
어떤 $y$가 존재해 $2^{y+1}$ 길이의 수열을 얻을 수 있다.
이 때의 범위는 $[2^y, 2^y + \text{Min}(N,\,2^{y+1} - 1)]$ 이다.
$2^y+2^{y+1} - 1 \le N$ 인 가장 큰 $y$와 $y+1$ 을 고려한다.
그러면 $\text{Max}(2^{y+1}, N - 2^{y+1}+1)$ 이 가장 긴 수열의 길이이다.
TBD
Comments