2026년 1월 23일

C - Mod of XOR

$X \lt C \oplus X$인 경우. $n = C \oplus X$에 대해 $(n \oplus C) \mod n = (C \oplus X \oplus C) \mod (C \oplus X) = X \mod (C \oplus X) = X$이므로 $n = C \oplus X$는 유효한 해이다.

$X \ge C \oplus X$인 경우. $\lfloor \log_2 C \rfloor \le \lfloor \log_2 X \rfloor$이므로 $C \lt 2X$이다. $(n \oplus C) \mod n = X$이므로 $2X < n$이다. $(n \oplus C) \mod n = X$의 해집합은 $(n \oplus C) - kn = X$의 해집합의 부분집합이다 ($k$는 음이 아닌 정수). 이진수 덧셈을 생각하면 $(n + C) = (n \oplus C) + 2(n \operatorname{AND} C)$이다. $0 \lt (n + C) - 2(n \operatorname{AND} C) - kn = X$이므로 $(k-1)n \lt C - 2(n \operatorname{AND} C) \le C \lt 2X \lt n$이고 $k$는 $0$ 또는 $1$이다. 따라서 $(n \oplus C) = X$와 $(n \oplus C) - n = X$의 해를 살펴보는 것으로 충분하다.

$(n \oplus C) = X$인 경우. $n = C \oplus X$이다.

$(n \oplus C) - n = X$인 경우. $\frac{C - X}{2} = n \operatorname{AND} C$이다. 정수 $A$를 $A = \frac{C - X}{2} \operatorname{AND} C$, 정수 $B$를 $B \operatorname{AND} C = 0$이라고 하자. $n = A + B$이다.

조건 $(n \oplus C > n)$. $n \oplus C = B + (A \oplus C) > A + B$이므로 이 조건은 $B$와 관계없이 결정된다.

조건 $(2X < n)$. $1 \le C, X \lt 2^{30}$, $1 \le n \lt 2^{60}$이므로 $B$를 적당히 큰 수로 정하는 것으로 충분하다.

결론. $(n \oplus C) \mod n = X$의 해집합과 집합 $\left\{C \oplus X, (\frac{C - X}{2} \operatorname{AND} C) + ((2^{60}-1) \oplus C) \right\}$의 교집합이 공집합인 경우는 해집합이 공집합인 경우 뿐이다.

트리 이사

$D$차원 공간에는 최대 $2D$개의 리프 노드를 놓을 수 있다. 다음과 같은 구성적 해를 찾을 수 있다. DFS를 할 때 $L$개의 리프 노드 중에서 $i$번째로 방문한 정점을 $l_i$라고 하자. 다음과 같은 순서 $u$를 만든다. $u = (l_1, l_{1 + \lfloor L/2 \rfloor}, l_2, l_{2 + \lfloor L/2 \rfloor}, \cdots, l_{\lfloor L/2 \rfloor}, l_{\lfloor L/2 \rfloor + \lfloor L/2 \rfloor})$. $L$이 홀수인 경우 마지막에 $l_L$을 추가한다. 초기 컴포넌트가 ${ u_1 }$이라고 할 때, 컴포넌트에서 리프 노드 $u_i$로 향하는 경로를 따라가며 단위 벡터 $(-1)^i \times \mathbf{e}_{\lfloor i / 2 \rfloor}$를 사용해서 정점의 위치를 확정하면서 컴포넌트에 추가한다.

Cards

$a$를 기준으로 오름차순으로 정렬하고 생각한다. $a$의 inversion과 $b$의 inversion의 차이를 $\Delta$라고 할 때 $\Delta$를 $0$으로 만드는 문제이다. 두 원소를 swap할 때 $\Delta$의 변화량은 $-2, 0, 2$ 중 하나이다. 따라서 $\Delta$가 홀수일 때는 $\Delta$를 $0$으로 만들 수 없다. $a$는 정렬되어 있으므로 $b$의 inversion을 계산해둔다. $b$를 기준으로 작은 수부터 최대한 앞으로 옮긴다. $\Delta$를 $0$으로 만들 수 있을 때에는 필요한 만큼만 앞으로 옮긴다. $b$가 정렬되었을 때의 inversion count는 $0$이고 한 번의 swap에 $\Delta$는 2씩 변하므로 $\Delta$가 짝수일 때 해가 존재함을 구성적으로 증명 가능하다.

Codeforces Round 1075 (Div. 2)

A. Table with Numbers

$h \ge l$을 가정하고 $h$보다 작거나 같은 $a_i$의 개수를 $p$, $l$보다 작거나 같은 $a_i$의 개수를 $q$라고 하자. 정답은 $\min \left( \left \lfloor \frac{p}{2} \right \rfloor, q \right)$이다.

B. The Curse of the Frog

$d = \sum_{i = 1}^n a_i \times (b_i - 1)$만큼 이동한 상태에서 생각하자. $1$원을 지불하면 $a_i \times b_i - c_i$만큼 더 이동할 수 있다. 그렇다면 $g = \max(a_i \times b_i - c_i)$만 사용하는 것이 이득이다. $g \le 0$이면 $d$만큼 이동한 것이 최선이다. $g > 0$이면 답은 $\max \left(0, \left \lceil \frac{x - d}{g} \right \rceil \right)$이다.

C1. XOR Convenience (Easy Version)

$p_i = i$인 순열에 대해 $\text{swap}(p_{2k}, p_{2k+1})$과 $\text{swap}(p_1, p_n)$을 순서대로 적용하면 유효한 순열을 구할 수 있다.

C2. XOR-convenience (Hard Version)

$n$이 홀수인 경우. $p = (n \oplus 1, 2 \oplus 1, 3 \oplus 1, \cdots, (n - 1) \oplus 1, 1)$은 문제의 조건을 만족한다.

$n$이 짝수이고 $n=2^k$인 정수 $k$가 존재하는 경우. $1 \le i < n$에 대해 $i \oplus n > n$이므로 $p_1, p_2, \cdots, p_{n-1}$에는 $n$을 배치할 수 없다. $p_n = n$이면 $(n - 1) \oplus p_{n-1} = n$을 만족하는 $p_{n-1}$가 없으므로 문제의 조건을 만족하는 $p$가 없다.
$n$이 짝수이고 $1 < 2^s < 2^{\lfloor \log_2^n \rfloor}$인 정수 $s$가 존재하는 경우. 순열 $p = (n, 2 \oplus 1, 3 \oplus 1, \cdots, (n-1) \oplus 1, 1)$에 $\text{swap}(p_{1}, p_{2^s})$를 적용하면 문제의 조건을 만족한다.