2026년 1월 30일

Codeforces Round 1077 (Div. 2)

A-C는 생략한다.

D. Shortest Statement Ever

구성적 해 또는 그리디 풀이가 존재할 것이라고 예상했지만 생각이 나지 않아서 $31 \times 2 \times 2$ 자릿수 DP를 4번 푸는 것으로 해결했다.
정해는 다음과 같다.
$x \& y = 0$일 때는 $p = x, q = y$로 놓을 수 있다. $x \& y \neq 0$일 때는 $i = \log_2{(x \& y)}$에 대해 $(p, q)$의 순서쌍 $(\lfloor \frac{x}{2^i} \rfloor \times 2^i + 2^i, y)$, $(\lfloor \frac{x}{2^i} \rfloor \times 2^i - 1, \lfloor \frac{y}{2^i} \rfloor \times 2^i)$, $(x, \lfloor \frac{y}{2^i} \rfloor \times 2^i + 2^i)$, $(\lfloor \frac{x}{2^i} \rfloor \times 2^i, \lfloor \frac{y}{2^i} \rfloor \times 2^i - 1)$를 확인하는 것으로 충분하다.

E. Jerry and Tom

지문이 복잡하지만 정리하면 트리 $T$에서 $d_u \le d_v$를 만족하는 순서쌍 $(u,v)$에 대해 $\sum (d_u - d_{\operatorname{lca}(u,v)})$를 계산하는 문제이다. $f(d)$를 $T$에서 깊이가 $d$인 정점의 개수라고 할 때 $\sum d_u = \sum d f(d) (f(d) + f(d + 1) + \cdots + f(N))$이고 이는 $O(N)$에 계산 가능하다. $\sum d_{\operatorname{lca}(u,v)}$는 어떤 간선이 $\operatorname{lca}(u,v)$와 루트를 연결하는 경로에 몇 번 포함되는가로 바꾸어서 풀 수 있다. 정점 $x$와 $x$의 부모 정점 $p$를 연결하는 간선이 사용되는 횟수는 $x$를 루트로 하는 서브트리의 $d_u \le d_v$를 만족하는 정점의 순서쌍 $(u,v)$의 개수와 같다. 집합 $S$에 하나의 정점을 추가할 때 순서쌍이 몇 개 추가되는지는 $S$에 포함된 깊이가 $d$인 정점의 개수와 $S$의 크기를 알면 구할 수 있다. small to large로 $O(N \log^2N)$ 또는 $O(N \log N)$에 계산한다.

ICPC 2023 Asia Yokohama Regional

Chayas

bit dp로 왼쪽부터 채워나가면서 모순이 발생하는지 판단하는 $O(2^n\times n \times n^2)$ 풀이를 떠올릴 수 있다. 이때 모순 판단을 sos dp(fast zeta transform)로 $O(2^n\times n)$에 전처리해 둘 수 있다.

내 풀이. $(a,b,c)$에 대해 $f(\{a, c\})+= 1$, $f(\{b\})+=1$, $f(\{a,b\})-=1$, $f(\{b,c\})-=1$를 기저로 하고 sos dp를 계산한다. $f(S) = 0$이고 $f(S \cup \{b\})=0$이면 집합 $S$에 $b$를 추가할 수 있다.

정해. $f(S)$는 왼쪽 집합이 $S$일 때 추가할 수 없는 $b$의 집합이다. 오른쪽 집합에 대해서도 모순을 판별해야 하는데 이는 $f(U - S)$을 보면 된다.

sos dp로 전처리를 하고 bit dp로 카운팅을 하면 $O(2^n \times n)$에 답을 구할 수 있다.