2026년 2월 5일

AtCoder Regular Contest 203 (Div. 2)

A - All Winners

각 팀에서 대표를 둘씩 뽑아서 매칭하면 모든 게임에 승리하는 사람을 $N$명 만들 수 있다. 각 그룹에 한 명씩 있는 경우 모든 게임에 승리하는 사람은 최대 한 명이다. 정답은 $\lfloor\frac{M}{2}\rfloor\times N + (M \bmod 2)$이다.

B - Swap If Equal Sum

$A = B$인 경우는 자명하다. $1$의 개수가 같고 popcount가 2 이상이면 항상 가능하다. popcount가 1인 경우 $100$, $001$과 같은 케이스를 고려하여 판단한다.

C - Destruction of Walls

$H\times W$ 격자 그래프에서 $K$개의 간선을 선택할 때 $(1,1)$과 $(H,W)$가 연결되는 경우의 수를 구하는 문제이다.
$K < H + W - 2$: 최단 경로보다 짧으므로 경우의 수는 $0$이다.
$K = H + W - 2$: 최단 경로의 개수와 같다. $\binom{H + W - 2}{H - 1}$
$K = H + W - 1$: 각각의 최단 경로에 하나의 간선을 추가한다. $\binom{H + W - 2}{H - 1} \times 2(H - 1)(W - 1)$
$K = H + W$: 각각의 최단 경로에 두 개의 간선을 추가한다. 중복의 개수는 $(H-1)\times (W-1)$ 격자 그래프에서 하나의 최단 경로가 격자점에 얼마만큼의 영향을 주는지 생각하면 구할 수 있다. $\binom{H + W - 2}{H - 1} \binom{2 (H - 1) (W - 1)}{2} - \binom{H + W - 4}{H - 2}(H + W - 3)$
최단 경로를 포함하지 않는 경로를 센다. $D$가 $H$개, $U$가 $1$개, $R$이 $W-1$개 있을 때 $D$, $U$, $R$ 순으로 격자를 벗어나거나 $D$와 $U$가 인접한 경우가 없도록 배치한다. $L$이 존재하는 경로는 이와 대칭적이다. $(H - 1)\binom{H + W - 2}{W - 3} + (W - 1)\binom{H + W - 2}{H - 3}$