250717 연습

카이스트에서 여는 몰입캠프에서 오전부터 저녁까지 개발하느라 ps를 조금 놓았다...

하지만 ucpc 예선도 치고, 2023 icpc yokohama regional도 푸는 등 심심할 때마다 문제를 풀었다.

 

1.1. Burnside lemma

group $G$의 $X$에 대한 group action의 orbit을 개수를 구하는 공식이다.

$$|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$$

여기에서 $|X/G|$는 orbit 개수, $X^g$는 $g = g \cdot x$인 $x$의 집합이다.

 

$g \cdot x = x$를 만족하는 $(g, x)$의 개수에 대한 double counting

$g$를 기준으로 하면 $\sum_{g \in G} |X^g|$이다.

$x$를 기준으로 하면 $\sum_{x \in G} |stab(x)| = \sum_{x \in G} \frac{|G|}{|orb(x)|} = \sum_{A \in X/G} \sum_{x \in A} \frac{|G|}{|A|} \cdot |A| = \sum_{A \in X/G} |G| = |G| \cdot |X/G|$이다.

 

회전해서 같아질 수 있는 목걸이를 같은 것으로 취급할 때 목걸이 개수 세는 문제를 풀 때 쓰인다.

1.2 Polya's enumeration Theorem

Burnside lemma에서는 각 목걸이를 $X$의 원소로 생각했다면, 여기는 각 목걸이 알갱이를 원소로 생각해서 burnside lemma를 재해석한다. 크게 대단한 아이디어는 없는 것 같다.

 

2. Ferris Wheel

2023 icpc 보스문제이다. 다항식 비빔밥으로 $O(nlogn)$에 풀었다. 뚫은걸지도 모른다. 하지만 이 문제에는 다항식 연산을 사용하지 않는 $O(nlogn)$ 풀이가 있다. 알아보자.

 

풀이를 읽어보면, 나머지는 다 할만하고 $(0, 0)$에서 (n, n)$까지 $y \leq x$ 부분만 타고 오른쪽 혹은 위쪽으로 이동하면서 $y=x$와 $k$번 닿는 경로의 개수를 구하는게 너무 어렵다. 리프의 도움을 받아서 풀이를 알아냈다. 이제 그것을 공개한다!

$(0, 0)$에서 $(n, n)$으로 $y \leq x$ 영역에서 이동하는 경로와 $(0, 0)$에서 $(n-1, n+1-k)$으로 $y \leq x$ 영역에서 이동하는 경로의 일대일대응이다. 놀랍게도 정말 열심히 그린 그림이다! 열심히 설명하려고 하면 너무 길어질 것 같다.

 

간단하게 설명하자면 $(0, 0)$에서 $(n, n)$으로 가는 경로에서 $y=x$에서 만나는 위치마다 위로 이동하는 이동을 빼주고 처음/마지막 이동을 빼주면 $(0, 0)$에서 $(n-1, n+1-k)$으로 $y \leq x$에서 이동하는 경로가 된다.

 

3. UCPC 2025 예선 F번을 푼 팀원의 1000B도 안 되는 코드 염탐하기

Fenwick tree로 prefix min/max를 아주 쉽게 관리할 수 있다.

std::range를 사용하면 sort(v.begin(), v.end())를 range::sort(v)로 간단하게 쓸 수 있다.