연습 250606

1. https://www.acmicpc.net/problem/31598

N범위 10^6, 소인수 개수를 P라고 할 때 O(PNlogN)에 짧은 구현으로 풀 수 있다. 시간제한이 5초라서 널널할텐데 괜히 N범위에 쫄아서 O(PN)에 짰다. 일정 길이 구간 최솟값을 구해야 되는데, 스위핑으로 하면 편한 걸 스위핑으로 안 해서 구현이 길어졌다.

 

2. https://www.acmicpc.net/problem/31603

정점 x에 대해 k번째 lca를 구해야 된다. m 이하의 조상 v에 대해 sub[par[v]] - sub[v]의 합이 k 이하인 m을 구해야 한다. pst로 range update + point query로 구현했다. (segtree 배열은 ett 인덱스 순) 

그런데 정점에 쓰여있는 번호 순으로 segtree 배열을 만들고 x에서 루트로 올라가는 path를 관리하면 그냥 스위핑으로 할 수 있다. 이분탐색을 세그트리에서 할 수도 있어서 로그도 하나 뗄 수 있다. (내 구현은 시간에 대한 이분탐색, 이 구현은 배열 위에서 이분탐색)

 

서브트리 내부 k번째 정점을 구하는 것도 pst를 사용했다. segtree 배열은 ett 인덱스 순으로, 시간은 정점 크기로 설정했다.

segtree 배열과 시간을 바꾸면, 시간에 대한 이분탐색을 배열 위에서 이분탐색으로 바꿀 수 있어 로그를 또 뗄 수 있다.

 

3. https://www.acmicpc.net/problem/20179

가로 길이가 2 이상인 단위(?)로 모인 컴포넌트에 하나의 가로 길이가 1인 단위(?)가 붙어있어도 처리할 수 있다. 그래서 가로 길이가 1인 단위를 위/아래 중 어디에 붙일지 01bfs로 한 점으로부터 거리를 구한 뒤에 결정했다. 그런데 dfs 한 방이면 그냥 자연스럽게 각 컴포넌트에 1개의 가로 길이 1인 단위가 붙는다. 리프 코드를 치팅해서 구현을 바꾸고 코드 길이를 반토막냈다. 

 

사소한건데, 구현할 때 복잡해지지 않는 선에서 여러 개를 한 번에 처리하는 것도 나쁘지 않은 것 같다.

긴 구현

짧은 구현

4. https://www.acmicpc.net/problem/33953

C=+K, P=-1로 산을 그리자. 어떤 높이가 0인 위치에서 앞뒤로 C가 있는 경우의 수를 구해야 한다. 포함과 배제로 문제를 풀자.

 

위치 i(K+1)와 (i+a)(K+1)에서 높이가 0인 경우, 사이에 있을 수 있는 산의 경우의 수를 f(a)라고 하자.

위치 a(K+1)에서 처음으로 높이가 0인 경우 앞에 산의 경우의 수를 g(a)라고 하자. 

위치 (N-a)(K+1)에서 마지막으로 높이가 0인 경우 뒤에 산의 경우의 수를 h(a)라고 하자.

 

sum_{i1 < i2 < .. < in} g(i1)f(i2-i1) f(i3-i2) .. f(in-i{n-1})h(N-in) * (-1)^in 을 구해야 한다.

이건 G(x) * H(x) * (1 + F(x) + F(x)^2 + ...) = G(x) H(x) / (1-F(x))을 구하면 된다. F, G, H는 f, g, h의 생성함수이다.

 

나는 online fft로 풀었다. 앞으로 online fft가 생각나면 생성함수를 한 번 생각해봐야겠다.