BOJ 10736 - XOR삼형제 2
Claim 1. 정답이 되는 가장 긴 수열 중 하나는 연속된 수들의 집합이다.
따라서 정답이 되는 수열 A가 A=[x,x+1,x+2,x+3,…] 이다.
x의 후보를 생각해본다.
∣A∣=k 라면 x∼x+k−1 까지의 어떤 세 수는 ⊕이 0이 아니여야 한다.
Lemma 1. x=2y 라면 항상 [2y,2y+2y+1) 범위의 수들을 포함할 수 있다.
2y⊕2y+1⊕2y+2y+1=0 이기 때문에 최대 범위는 2y+2y+1−1 이다.
[2y,2y+2y+1) 에 존재하는 서로 다른 세 수 α,β,γ 를 고려한다.
α⊕β∈[2y,2y+2y+1) 임을 보이면 된다.
wlog.α<β 이라 하자.
α<β<2y+1 → α⊕β의 가장 큰 bit는 최대 2y−1 이기 때문에 옳다.
α<2y+1≤β → α⊕β 는 2y, 2y+1 bit가 1이고 이런 수는 범위내에 없다.
2y+1≤α<β → α⊕β의 가장 큰 bit는 최대 2y−1 이기 때문에 옳다. □
Claim 2. Claim 1이 참이라면, 항상 x=2y 이다.
어떤 y가 존재해 2y+1 길이의 수열을 얻을 수 있다.
이 때의 범위는 [2y,2y+Min(N,2y+1−1)] 이다.
2y+2y+1−1≤N 인 가장 큰 y와 y+1 을 고려한다.
그러면 Max(2y+1,N−2y+1+1) 이 가장 긴 수열의 길이이다.
TBD
Comments