2026년 2월 2일

JAG Summer Camp 2023 Day 3

Roller Coaster

-

Break a Prison

BFS.

Camp room assignment

주어진 $m$에 대해 정답 수열을 $A_n$($1 \le n \le m$)이라고 하자. $S_n = \sum_{i=0}^{n-1}{\binom{2n}{i}(m-1)^i}$에 대해 $A_n = m^{2n} - mS_n$이다. 이는 $O(m^2)$에 계산 가능하고 이를 최적화하는 방법은 3가지 정도가 존재한다.
방법 1. $\binom{n}{k}=\binom{n-1}{k} + \binom{n-1}{k-1}=\binom{n-2}{k}+2\binom{n-2}{k-1}+\binom{n-2}{k-2}$라는 사실을 이용하면 점화식 $S_{n+1}=m^2S_n+(m-1)^n\binom{2n}{n}-(m-1)^{n+1}\binom{2n}{n-1}$을 얻을 수 있다.
방법 2. 어떤 상수 $C$를 기준으로 $n \le C$인 $A_n$은 $O(C^2)$에 직접 구한다. $C < n$인 $A_n$은 find p-recursive 알고리즘으로 $O(C^3+mkd)$에 구한다.
방법 3. FPS(생성 함수)와 분할 정복으로 $O(m\log^2m)$에 계산 가능하다고 한다.

Gacha 101

다음의 문제를 해결할 수 있다면 이 문제를 풀 수 있다.

$N$가지 색에 대해 $i$번째 색으로 칠해진 공이 $a_i$개 있다. 주머니에 $S = \sum_{i=1}^{N}{a_i}$개의 공이 들어있고 각각을 뽑을 확률을 모두 같다. 주머니에서 공을 하나씩 뽑아서(비복원추출) 길이가 $S$인 배열을 왼쪽부터 차례대로 채운다. 배열에서 색상 $i$로 칠해진 공이 처음 등장하는 위치를 $f_i$라고 하자. $f_1 < f_2 < \cdots < f_N$일 확률을 구하시오.

색상 $1$부터 색상 $N$까지 차례대로 빈 칸중 첫 번째 칸을 무조건 채우도록 하며 확률을 계산한다.

$$\frac{\binom{S - 1}{a_1 - 1}\times a_1!}{\binom{S}{a_1}\times a_1!} \times \frac{\binom{S -a_1 - 1}{a_2 - 1}\times a_2!}{\binom{S - a_1}{a_2}\times a_2!} \times \cdots \times \frac{\binom{a_N - 1}{a_N - 1}\times a_N!}{\binom{a_N}{a_N}\times a_N!} = \frac{a_1}{S} \times \frac{a_2}{S-a_1} \times \cdots \times \frac{a_N}{a_N}$$

Best parentheses

가중치가 있는 괄호로 구성된 문자열 $S$의 subsequence $T$ 중에 유효한 괄호 문자열이면서 가중치의 합이 최대인 $T$를 찾는 문제이다. $O(N^2)$ DP가 불가능하므로 그리디가 정해일 것이라는 강한 확신이 있다. 우선 가중치 합이 음수인 괄호 쌍은 제거하는 것이 최적이다. 왼쪽에서 오른쪽으로 순회하면서 열린 괄호의 가중치를 우선 순위 큐로 관리한다. 닫힌 괄호를 만나면 매칭이 가능한 경우 매칭하고, 더 나은 매칭이 발견될 수 있으므로 자신의 가중치에 $-1$을 곱해서 우선 순위 큐에 넣는다.

Edit distance on table

Levenshtein distance의 정의에 맞게 상태 전이를 작성하고 나서 보면 $|S|$가 무한히 커질 수 있다는 특징에 의해 사이클이 발생한 것을 확인할 수 있다. 일반적인 편집 거리 계산처럼 DP를 사용할 수는 없지만 목표는 최단 경로를 구하는 것이므로 0-1 BFS 또는 Dijkstra's를 사용하면 된다.

---

편집 거리

DP 점화식은 Levenshtein distance의 정의에 맞게 작성한다. DP 계산에 필요한 메모리는 슬라이딩 윈도우로 $O(N)$으로 최적화하고, 역추적에 필요한 메모리는 bitset으로 $O(\frac{N^2}{W})$로 최적화한다.