BOJ 10736 - XOR삼형제 2

image.png

Claim 1. 정답이 되는 가장 긴 수열 중 하나는 연속된 수들의 집합이다.

따라서 정답이 되는 수열 AAA=[x,x+1,x+2,x+3,]A=[x,x+1,x+2,x+3,\dots] 이다.

xx의 후보를 생각해본다.

A=k\vert A \vert=k 라면 xx+k1x \sim x+k-1 까지의 어떤 세 수는 \oplus00이 아니여야 한다.

Lemma 1. x=2yx=2^y 라면 항상 [2y,2y+2y+1)[2^y, 2^y + 2^{y+1}) 범위의 수들을 포함할 수 있다.

2y2y+12y+2y+1=02^y \oplus 2^{y+1} \oplus 2^y+2^{y+1}=0 이기 때문에 최대 범위는 2y+2y+112^y+2^{y+1}-1 이다.

[2y,2y+2y+1)[2^y,2^y+2^{y+1}) 에 존재하는 서로 다른 세 수 α,β,γ\alpha, \beta, \gamma 를 고려한다.

αβ∉[2y,2y+2y+1)\alpha \oplus \beta \not\in [2^y, 2^y+2^{y+1}) 임을 보이면 된다.

wlog.α<βwlog. \alpha < \beta 이라 하자.

α<β<2y+1\alpha < \beta < 2^{y+1} \rightarrow αβ\alpha \oplus \beta의 가장 큰 bit는 최대 2y12^{y-1} 이기 때문에 옳다.

α<2y+1β\alpha < 2^{y+1} \le \beta \rightarrow αβ\alpha \oplus\beta2y, 2y+12^y,~2^{y+1} bit가 11이고 이런 수는 범위내에 없다.

2y+1α<β2^{y+1} \le \alpha < \beta \to αβ\alpha \oplus \beta의 가장 큰 bit는 최대 2y12^{y-1} 이기 때문에 옳다. \square

Claim 2. Claim 1이 참이라면, 항상 x=2yx=2^y 이다.

어떤 yy가 존재해 2y+12^{y+1} 길이의 수열을 얻을 수 있다.

이 때의 범위는 [2y,2y+Min(N,2y+11)][2^y, 2^y + \text{Min}(N,\,2^{y+1} - 1)] 이다.

2y+2y+11N2^y+2^{y+1} - 1 \le N 인 가장 큰 yyy+1y+1 을 고려한다.

그러면 Max(2y+1,N2y+1+1)\text{Max}(2^{y+1}, N - 2^{y+1}+1) 이 가장 긴 수열의 길이이다.

TBD

Tags:

Categories:

Updated:

Comments