2026년 2월 3일

JAG Summer Camp 2023 Day 3

Odd trip plans

동적 그래프 $G$에서 정점 $u$에서 시작해서 정점 $v$에서 끝나는 walk 중에 $1,2,\cdots,N$의 모든 정점을 홀수번 방문하는 walk가 존재하는지 판별하는 문제이다. $G$는 연결 요소라고 가정한다. Walk $W$에서 정점 $u$의 빈도를 $f_u$, $W$의 길이를 $L$이라고 할 때, $f_u \equiv 1 \pmod 2, \forall u \in G$와 $L \equiv N - 1 \pmod 2$는 필요충분조건이다.
$f_u \equiv 1 \pmod 2, \forall u \in G \implies L \equiv N - 1 \pmod 2$
$\sum_{i=1}^N {f_i} \equiv \sum_{i=1}^N{1} \equiv N \pmod 2$이다. $\sum_{i=1}^N{f_i} = L + 1$이다. 따라서 $L \equiv N - 1 \pmod 2$이다.
$L \equiv N - 1 \pmod 2 \implies f_u \equiv 1 \pmod 2, \forall u \in G$
$\sum_{i=1}^N{f_i} \equiv L + 1 \equiv N \pmod 2$이다. $f_i$ 중 짝수의 개수를 $k$라고 하자. $\sum_{i=1}^N{f_i} \equiv N - k \equiv N \pmod 2$ 이므로 $k$는 짝수이다. 모든 정점을 적어도 한 번 지나는 walk $W$를 하나 선택한다. $f_u \equiv f_v \equiv 0 \pmod 2$인 서로 다른 정점의 쌍 $(u, v)$에 대해 $u$와 $v$를 연결하는 경로를 하나 선택한다. $W$에서 하나의 $u$를 제거하고 그 위치에 $u \rightarrow \cdots \rightarrow v \rightarrow \cdots \rightarrow u$를 넣으면 $f_u$와 $f_v$의 홀짝성만 변하고 다른 정점의 홀짝성에는 영향을 주지 않는다. 짝수인 $f_u$가 짝수개 있으므로 모든 $f_u$를 홀수로 만들 수 있다.
$u$에서 시작해서 $v$에서 끝나는 길이의 홀짝성이 $N$의 홀짝성과 반대인 walk가 존재하는지 판별하는 문제를 해결한다.
$G$에 홀수 사이클이 있다면 임의의 walk의 홀짝성을 뒤집을 수 있다.
$G$에 홀수 사이클이 없다면 $G$는 이분 그래프이다. 이분 그래프에서 $u$에서 시작해서 $v$에서 끝나는 모든 walk의 홀짝성은 같다. $u$와 $v$가 같은 그룹에 있는지 판별 가능하다면 정답을 알 수 있다.
xor abelian group에 대해 모든 간선 가중치가 $1$인 potential graph를 rollback disjoint set과 offline dynamic connectivity로 관리한다. 이때 potential graph에 모순이 있다면 홀수 사이클이 존재하는 것이다. 모순이 없는 경우 $u$와 $v$의 퍼텐셜 차이를 계산하여 정답을 구한다.

AtCoder Regular Contest 205 (Div. 2)

A - 2x2 Erasing

부분 격자에 포함된 서로 다른 흰색 $2\times 2$ 격자의 개수가 답의 상한이고 이는 항상 구성 가능하다. $2\times 2$ 격자의 좌상단을 기준으로 전체 격자를 전처리하고 누적합을 계산해서 쿼리를 처리한다.

B - Triangle Toggle

삼각형 연산을 적용해도 정점의 degree의 홀짝성은 변하지 않는다. $\deg(u) \equiv N - 1 \pmod 2$인 정점은 $\deg(u) = N-1$, $\deg(u) \not\equiv N - 1 \pmod 2$인 정점은 $\deg(u) = N-2$가 최선이고 이는 항상 구성 가능하다. 두 개의 흰 색 간선을 가진 정점을 선택해서 연산을 적용하면 검은색 간선은 하나 이상 증가한다.

C - No Collision Moves

우선 방향을 무시하고 어떤 구간이 다른 구간을 완전히 포함하면 불가능하다. 이러한 구간이 없다고 할 때 다시 방향을 고려해서 방향이 서로 다른 두 벡터가 겹치는 부분이 있으면 이는 불가능하다. 이러한 벡터도 없다면 방향이 바뀌는 곳 마다 칸막이를 놓을 수 있고 서로 다른 칸의 벡터는 독립이다. 같은 칸의 벡터는 벡터의 방향에 따라 올바른 방향으로 순회하는 것으로 정답을 구할 수 있다.

D - Non-Ancestor Matching

서브트리의 루트는 서브트리에 포함된 정점과 매칭할 수 없다. 가장 큰 서브트리의 크기가 과반수 이하가 될 때까지 재귀적으로 서브트리를 분할한다. 이전에 분할한 서브트리가 있다면 루트를 매칭할 수 있다. 모든 서브트리의 크기가 과반수 이하라면 완전 매칭이 존재한다.
Tutte–Berge formula를 활용한 풀이가 존재한다.