Class 8

Class 8을 달았다.

Class 8에 처음? 등장하는 FFT / 플로우 / DnC opt 등을 공부하긴 귀찮고 그렇다고 국메기같은 굉장한 문제를 짜긴 싫어서, 최대한 구현이 편해보이고 이미 알고 있는 지식으로 풀 수 있는 문제들을 열심히 찾아서 풀었더니 딱 20문제가 됐다.

 

 

풀면서 재미 또는 감동이 있었던 문제에 대해 간략하게 사고과정과 풀이를 작성한다.

 

레드 블루 스패닝 트리 #4792

파란색 간선을 최소로 써서 MST를 만들어 그때 파란색 간선이 몇개인지 세고,

파란색 간선을 최대로 써서 MST를 만들어 그때 파란색 간선이 몇개인지 세면,

그 사이에 개수가 답이 될 수 있다.

 

풀이 자체는 n년 전부터 알고 있었는데, 이왕 푸는거 증명까지 해보기로 했다.

현재 MST에 파란색 간선이 x개 있을 때, 아래와 같은 과정을 통해 파란색 간선을 하나 추가할 수 있다. (단, 현재 파란색 간선의 개수가 최대가 아님)

 

일단 파란색 간선만 있는 그래프를 생각해 보자. 이 그래프에서 컴포넌트 개수를 C라고 하자.

현재 MST에서 파란색 간선만 남기면, 스패닝 포레스트?가 있을 것이다. 현재 파란색 간선의 개수가 최대가 아니니까, 이 스패닝 포레스트의 컴포넌트 개수는 C 초과일 것이다. 또한 이 스패닝 포레스트의 두 컴포넌트를 이을 수 있는 스패닝 포레스트에 포함되지 않은 파란색 간선이 있을 것이다. 이 파란색 간선을 추가하고, 원래 두 컴포넌트를 잇던 빨간색 간선을 삭제하면 된다.

 

빨간색 간선에 대해서 똑같은 논리를 적용하면 파란색 간선 하나 삭제도 설명할 수 있다.

달리기 #12963

내가 플로우의 ㅍ자도 몰라도, 최대 유량을 구하라는건 안다...

가중치가 $3^k$다. 여기서 나오는 성질을 잘 쓰면 플로우 없이 풀 수 있는 문제라서 Class 8에 있는거 아닐까... 하는 생각을 했다.

$i$번 간선의 가중치가 $3^i$니까, 더 작은 번호의 간선을 아무리 써도 $i$번 간선에는 자리가 남는다.

간선의 가중치를 내림차순 그래프에 추가하면서, $0$번 정점과 $N-1$번 정점이 이어지는 순간을 체크하면 되겠다.

$i$번 간선을 추가한 순간  $0$번 정점과 $N-1$번 정점이 이어졌다면, $i$번 간선을 가득가득 쓸 수 있다는 뜻이다. 답에 $3^i$를 더하고, 이제 $i$번 간선은 너덜너덜해졌으니까 그래프에서 지운다.

빌라봉 #8872

포레스트에 가중치가 상수 $L$인 간선을 몇개 추가해 트리를 만들고, 이때의 지름을 최소화해야한다.

컴포넌트가 딱 두개 있는 상황을 생각해 보자. 각 컴포넌트의 어디를 연결해야 될까...

가장 먼 점과의 거리가 최소인 점을 컴포넌트마다 뽑아서 연결시켜주면 되겠다.

일단 각 컴포넌트마다 가장 먼 점과의 거리가 최소인 점을 각각 뽑아주자.

이제 어떻게 연결하지?

그냥 가장 먼 점의 거리의 최솟값이 가장 큰 컴포넌트를 중심으로 해서, 성게 모양으로 이으면 되겠다.

 

트리의 지름을 구할 때 '아무 정점을 골라 거기서 가장 A를 찾고, A에서 가장 먼 정점 B를 찾으면 A-B가 트리의 지름이다'라는걸 어디서 줏어들은 적은 있어서 구현에 활용을 했는데, 증명은 모른다. 일단 귀찮아서 넘겼다.

점프 #17613

i번 연속으로 거리를 늘려가면서 점프하면 $2^0+2^1+\cdots +2^i=2^{i+1}-1$ 만큼 이동한다.

이걸 그리디 하게 반복하면 최소 점프 횟수가 될 것이다.

구간의 최댓값을 구해야 되는데, 구간의 길이 scale이 ${10}^9$니까, 뭔가 로그 또는 로그제곱으로 풀릴거 같다는 생각을 했다.

 

구간을 마지막에 연속 점프한 횟수를 기준으로 재귀적으로 분할해 문제를 풀자. $i$번 연속 점프하려면 $2^{i+1}-1$ 이상이어야 하므로, 구간은 대충 로그개로 나눠질 것이다. 이때 대부분의 경우 구간이 $[2^k-1,2^{k+1}-2]$ 꼴로 나눠질테니 (약간 세그먼트트리 바이브로) 구간에 대한 답을 map 등에 메모이제이션하면 빠르게 돈다. 아마도 로그제곱?? 인듯

사수아탕 #2419

사탕을 먹는데 시간이 들지 않으므로, 최적해에 포함된 사탕들은 연속된 구간을 이룰 것이다. 아니라면 그냥 지나가는 사이에 먹으면 되니까...

일단 $dp[s][e]$ := $[s,e]$구간의 사탕을 전부 먹는 최적해 형태로 생각을 해본다. 아하... 시간이 얼마나 흘렀는지를 모르니 구간을 늘릴 때 몇개의 사탕을 먹게될지를 모르니 dp 전이에서 얼마나 더해줄지를 모른다.

 

사탕의 개수가 음수가 될 수도 있다고 하자. 이렇게 해도 답은 제대로 구할 수 있다.

최적해가 $a_1,a_2,\cdots ,a_k$위치의 사탕을 순서대로 먹는거라고 해보자. 

$0$에서 $X_{a_1}$ 까지 이동해 $M-abs(X_{a_1}-0))$만큼의 사탕을 먹고,

$X_{a_1}$에서$X_{a_2}$까지이동해$M - abs(X_{a_1} - 0) - abs(X_{a_1} - X_{a_0} ) )$만큼의 사탕을 먹고,

...

$M\times k$에 각 $i$에 대해 $i\times (X_{a_i}-X_{a_{i-1}})$만큼 빼준 값만큼 사탕을 먹게된다.

아~ $k$를 고정하고 dp를 돌리면 되겠다.

경주 #5820

센트로이드 분할은... 왠지 모르게 거부감이 든다.

스몰투라지로 {거리, 정점 개수} map을 관리한다.

map의 전체 원소에 x만큼 더하는 연산이 필요한데, map별로 offset을 따로 저장해두면 O(1)에 할 수 있다.

수열과 쿼리 4 #13546

개뻔한모스...인데

각 수의 위치를 deque로 관리하는건 뭔가 sexy하지 못하다는 생각이 들었다.

어쨌든 루트질로 잘 풀 수 있다. 한번도 안해본 형태의 루트질이었는데 글로 설명하려니까 어렵다.

http://boj.kr/9f3eac1169ca4d76ac69a4c767966a0a

사실 쿼리 처리 순서 자체는 모스랑 똑같다.

이거 풀면 수열과 쿼리 0도 부분합 배열 만들고 복붙하면 풀 수 있다. 개꿀