PS 연습 3

1/19 ~ 2/22

위 기간 동안 2차 선발고사를 대비해 문제를 풀었다.

 

1/19(일) - 1(?)일차

BOJ 25014 열차의 이동

무려 자력으로 풀었다.

경로 P에서 Q로 이동하는 과정을 생각해보자.

P에서 Q에 가장 가까운 정점을 x1, Q에서 P에 가장 가까운 정점을 x2라고 하자.

그러면 이동 과정을 다음과 같이 나타낼 수 있다.

1. P를 둠칫둠칫해서 P의 끝점을 x1으로 옮기기.

2. x1으로 옮긴 끝점을 x2로 옮기기

3. 끝점이 x2인 경로를 둠칫둠칫해서 Q로 옮기기.

1과 3은 뒤집으면 같은 과정이므로 1, 2만 처리해주면 되는데, 2는 그냥 자명하다.

그래서 1(둠칫둠칫)을 잘 처리해주면 된다.

경로를 일자로 폈을 때 각 정점별로 최대 깊이를 구하자.

이 정보를 활용해 적당히 투 포인터 + DP를 하면 된다.

LCA를 적절히 활용해 모든 정보를 구할 수 있으므로, $O(\sum |P|logN)$에 문제를 해결할 수 있다.

왜인지는 모르겠는데 이번에도 상수 최적화를 잘 해줘야 AC가 나왔다.

1/20(월) - 2일차

IOI 2024 Day 1을 돌았는데, 조졌다.

대충 푼 문제와 업솔빙한 문제의 풀이만 쓰겠다.

BOJ 32266 Nile

D가 고정된 값이라면 다음과 같이 문제를 해결할 수 있다.

우선 W[i]를 기준으로 물건을 정렬하고, 인접한 두 물건의 W의 차이가 D 이하라면 같은 그룹으로 묶어준다.

이 때 그룹의 크기가 짝수라면 모두 선택할 수 있다.

그룹의 크기가 홀수라면 하나를 배제하고 나머지를 선택하는 것이 최적일 것이다.

그룹에서 (홀수 번째 물건 중 최솟값)과 (짝수 번째 물건 중 좌우 물건의 W 차이가 D 이하인 것 중 최솟값) 중 작은 것을 버리면 된다.

D에 대한 쿼리는 D에 대해 오름차순으로 정렬하고 Union-Find를 진행하며 해결하면 된다.

BOJ 32265 Message

지리는 최적화를 하면 풀린다.

만점 풀이의 아이디어가 좀 신기한데, 80점대 풀이는 그래도 떠올릴 만은 한 것 같다.

1/21(화) - 3일차

27291, 20065, 17185, 25437로 이루어진 셋을 돌았다.

BOJ 27291 Grapevine

대충 센트로이드 트리 + 오일러 경로 테크닉 + 레이지 프로퍼게이션을 짜면 맞는다.

센트로이드 구현이 좀 익숙해진 것 같다.

BOJ 17185 Alpine Valley

트리에서 E를 루트로 두자.

R이 막힌 도로의 서브트리에 포함되지 않는다면 무조건 탈출 가능하다.

R이 막힌 도로의 서브트리에 포함된다면 답을 희소 테이블로 적당히 구할 수 있다.

BOJ 25437 Connected Towns

5N 풀이는 쉽다.

여기서 4N으로 줄이는 과정이 꽤 어려웠다.

우선 루트에 정점을 붙이는 것을 반복해 트리를 만들자. 이 트리의 특징은 각 정점의 첫 번째 자식을 제외한 모든 노드는 리프 노드라는 것이다.

여기서 홀수 깊이의 정점 중 후보를 하나 남기고, 짝수 깊이의 정점 중 후보를 하나 남길 것이다.

이 때 루트와 홀수 깊이 정점 후보가 인접하지 않거나 홀수 깊이 정점 후보와 짝수 깊이 정점 후보가 인접하지 않으면 셋 중 하나를 배제시킬 수 있다.

따라서 세 정점이 모두 인접한 경우가 최악의 경우이다. 이 경우에 앞에서 썼던 쿼리를 활용할 수 있도록 해야 한다.

이는 홀수 깊이 정점 후보를 남길 때 루트의 첫 번째 자식부터 보는 방식으로 해결할 수 있다.

BOJ 20062 Seats

굉장히 신기한 문제라고 생각한다.

어떤 상태가 있을 때, 그 상태에서 꼭짓점이 4개일 필요충분조건이 그 상태가 직사각형임을 이용한다.

이 아이디어를 알아냈으면 레이지로 적당히 처리할 수 있다.

1/22(수) - 4일차

웰노운 다이아 4 문제들을 좀 풀었다.

BOJ 1626 두 번째로 작은 스패닝 트리

최소 스패닝 트리를 아무거나 하나 잡고, 그 간선 중 하나를 다른 간선으로 대체했을 때 가능한 최소의 두 번째로 작은 스패닝 트리를 lca를 활용해 구할 수 있다.

BOJ 10806 공중도시

사이클이 있는 부분을 하나의 정점으로 압축하면 트리가 된다.

이 때 답은 (트리의 리프의 개수 + 1)/2가 되고, 적당히 construct하면 된다.

DFS ordering 기준으로 절반 차이나는 애들끼리 묶어주면 된다.

BOJ 13174 괄호

(를 +1, )를 -1이라 하고 a[i][j]=(i번째 괄호까지 봤을 때 현재까지 합이 j인 경우의 수)라 하면, 답은 a[n][0]+...+a[n][n]이 된다.

a[i][j]=Ka[i-1][j-1]+a[i-1][j+1](j!=0), a[i][0]=a[i-1][1]이므로 b[i]=a[i][0]+...+a[i][i]라 하면 b[i]=(K+1)b[i-1]-a[i-1][0]이 성립한다. 이 때 a[i-1][0]은 i가 짝수인 경우 0이고, i가 홀수인 경우 c[(i-1)/2]*k^((i-1)/2)이다.(단, c는 카탈란 수열이다.)

이를 대충 구현해주면 된다.

BOJ 11808 마리오와 사악한 키노피오

DP[i][j]를 i를 루트로 하는 서브트리에서 j개 방문하는 최장 경로 길이라고 하고 적당히 구하면 된다.

i를 루트로 하는 서브트리에서 방문하는 정점의 개수를 x개라 하면, i와 i의 부모를 연결하는 간선을 min(x, K-x+1)번 지나는 construction이 항상 존재한다.

BOJ 18252 별이 빛나는 밤에

가장 위 별과 가장 아래 별을 이은 직선을 생각하자.

각 레일에서는 별을 항상 이 직선에 가장 가까운 점만 고르면 된다는 것을 알 수 있다.

이제 최대 삼각형의 넓이를 계산해야 하는데, 이는 볼록껍질 + 투 포인터로 잘 할 수 있다.

1/23(목) - 5일차

27937, 15864, 21768, 21793로 이루어진 셋을 돌았다.

BOJ 27937 간단한 쿼리 문제

문제 제목과 다르게 결코 간단하지 않다.

일단 간단한 루트 로그 풀이를 알아낼 수 있는데, 로그를 붙이면 죽어도 안 돌 것 같으니 로그를 떼야 한다.

스윕 라인 모스라고 불리는 테크닉인 것 같은데, 난 적당히 하다 보니 풀렸다.

일단 모스에서 업데이트를 진행하는 부분에 로그가 붙어서 문제인 것인데, 이를 스위핑을 하면서 계산할 것이다.

스위핑을 하면서 계산할 때에도 제곱근 분할법을 사용해야 한다.

근데 이렇게 하면 메모리가 터져서 구간은 하나로 묶어서 세야 한다.

풀이가 상당히 대충인 것 같다.

BOJ 21768 AND PLUS OR

이것저것 해보다 보면 결국 i와 j가 최대 두 비트 차이 나는 조합만 시도해보면 된다는 것을 알 수 있다.

구현은 매우 간단한데, 발상이 미친듯이 어려운 것 같다.

BOJ 21793 Event Hopping 2

구간을 오른쪽 끝점 기준으로 정렬하고, 희소 테이블에 각 구간 별로 오른쪽으로 갈 수 있는 최소 구간을 저장해둔다.

이제 사전순으로 하나씩 고르면서 이 구간을 골라도 전체 k개 이상 고를 수 있는지 여부를 보면서 골라가면 된다.

BOJ 25440 송신탑

일단 41점까지는 간단하게 받을 수 있다.

x<y<z일 때 송신탑 x, y와 y, z가 통신할 수 있으면 x, z도 통신할 수 있음을 관찰하고 적당히 짜면 41점이 나온다.

섭테 5의 아이디어가 제일 중요한데, L=0, R=N-1으로 일정한 조건이 있는 경우이다.

일단 송신탑에서 극댓값, 극솟값만 중요하고 나머지는 제거해줘도 된다.

이제 인접한 두 탑의 높이의 차가 최소인 것이 D 미만이라면 두 탑을 모두 제거해줘도 된다.(둘 다 사용하지 않는 최적해가 존재한다.)

이를 반복하면 인접한 두 탑의 높이의 차는 최소 D 이상일 것이고, 이 때 전체 탑의 개수를 세주면 된다.

이 때 D가 변하더라도 제거하는 탑의 순서는 변하지 않으므로, 탑을 제거하는 것을 반복하면서 탑의 개수를 세주면 된다.

물론 양끝점 처리는 잘 해야 된다.

L, R이 바뀌더라도 문제를 비슷하게 풀 수 있는데, 전체 탑에서 D 미만인 것을 제거한 뒤에 구간에서 양끝에 최대 1개씩 더 추가되므로 이를 세그먼트 트리로 구하면 된다.

또한 탑을 제거해가는 과정을 PST로 저장해두면 L과 R 사이에서 임의의 시점의 탑의 개수를 알 수 있다.

1/24(금) - 6일차

USACO February Platinum을 돌았다.

BOJ 27841 Problem Setting

DP[i]를 비트가 i인 원소로 끝나는 경우의 수라고 하면, DP[i]는 j가 i에 포함되는 모든 비트 j에 대해 DP[j]의 합에 비트가 i인 수의 개수에 대한 적당한 값의 곱이다.

이를 그냥 SOS DP로 계산하면 안되고, i의 비트수가 0인 것부터 m인 것까지 차례로 SOS DP를 m번 돌려주면 된다.

1/26(일) - 7일차

BOJ 25015 아이싱

주어진 그래프의 DFS 트리를 구성했다고 하자.

이 때 DFS 트리의 back edge 중 홀수 사이클을 만드는 것과 짝수 사이클을 만드는 것으로 나눌 수 있다.

어떤 한 개의 간선을 제거해 그래프를 이분 그래프로 만들 필요충분조건은 모든 짝수 사이클에 포함되지 않고, 모든 홀수 사이클에는 포함되는 것이다.

어떤 두 개의 간선을 제거해 그래프를 이분그래프로 만들 필요충분조건은 모든 짝수 사이클에 포함되지 않거나 2개가 모두 포함되고, 모든 홀수 사이클에는 정확하게 하나의 간선만 포함되는 것이다.

이는 모든 백 엣지에 랜덤한 태그를 붙이고 xor하는 방식으로 체크해줄 수 있다.

Codeforces #1001 Div.1+Div.2

따로 후기를 작성했다.

1/27(월) - 8일차

USACO 2025 January Platinum Contest에 응시했다. 매우 어려웠다.

1차 선발고사 문제들이 백준에 올라와서 코드를 모두 제출했다.

BOJ 15864 Alternating Current

일단 완전히 포함 관계인 두 구간이 있으면, 그 두 구간이 다른 색으로 칠해지는 것이 최적임을 보일 수 있다.

따라서 완전히 포함되는 구간을 모두 제거하고, 포함 관계가 아닌 구간들만 남길 수 있다.

포함관계가 아닌 구간을 왼쪽 끝 기준으로 정렬하면 오른쪽 끝점의 위치도 단조 증가할 것이다.

이 때 구간의 개수가 짝수이면 10101...로 배정하는 것이 최적이고, 구간의 개수가 짝수라면 10101...로 배정하되 1이 연속한 부분이 한 개 있게 배정하는 것이 최적이다.

이는 귀류법으로 증명할 수 있다. 편의상 구간의 개수가 짝수인 경우만 증명할 것이다.

가능한 해가 존재하지만 위와 같이 배정했을 때 불가능하다고 가정하자.

그러면 0 또는 1로 커버되지 않는 지점 x가 존재할 것이다. x를 0과 1로 둘다 커버하지 못한다면 가능한 해도 존재하지 않을 것이다.

그러면 x를 0과 1 중 하나만 커버할 수 있는 경우를 따져야 하는데, 0으로만 커버할 수 있다고 하자.

그러면 0으로 x를 커버하는 구간을 i번 구간이라고 하면 i-1번 구간과 i+1번 구간은 둘다 x를 포함할 수 없다.

그럼에도 불구하고 가능한 해가 존재한다는 것은 i번 구간에 완전히 포함되는 구간이 존재하여 그 구간에 1이 배정되었다는 것이다.

이에 따라 0101...으로 배정했을 때도 x를 1번으로 덮을 수 있게 된다.

따라서 가능한 해가 존재한다면 0101...으로 배정해도 가능함을 증명할 수 있다.

짝수일 때는 그냥 해보면 되고, 홀수일 때는 느리게 갱신되는 세그먼트 트리를 이용해 빠르게 N가지 경우를 모두 시도해볼 수 있다.

1/28(화) - 9일차

24945, 24943, 21853, 27845으로 이루어진 셋을 돌았다.

BOJ 27845 Piling Papers

DPa[l][r][i][j][k]를 A[l...r]을 고려했을 때 a의 자릿수에서 i번째 위치부터 j번째 위치까지 차지했을 때 a보다 작으면 k=0, a와 같으면 k=1, a보다 크면 k=2로 하고, DPb를 비슷하게 정의할 수 있다.

이 DP를 잘 계산해주면 O(N^2K^2)에 DP 값을 모두 계산할 수 있고, 쿼리가 들어올 때마다 답을 빠르게 계산할 수 있다.

BOJ 24945 Copy and Paste 3

DP[l][r]를 S[l...r]을 만드는데 필요한 최소 비용이라고 하자.

DP[l][r]=Min{DP[l+1][r]+A, DP[l][r-1]+A, DP[l'][r']+B+C*(x := l'...r'가 등장하는 횟수)+A*(r-l+1-x(r'-l'+1))}으로 계산할 수 있다.

이를 Naive하게 계산하면 O(N^5)가 된다.

이 때 l'=l 또는 r'=r이 아니라면 DP[l+1][r] 또는 DP[l][r-1]에서 고려되었을 것이므로 l'=l 또는 r'=r이라고 할 수 있다.

이를 계산하면 O(N^4)가 된다.

이 때 l', r'에 대해서 해시와 희소 테이블을 활용해 l'...r'이 등장하는 횟수를 빠르게 구할 수 있다.

이렇게 하면 O(N^3logN)이 된다.

이제 l', r' 입장에서 l, r에 업데이트를 해준다고 생각하자. 하나의 l', r'에 대해서 업데이트해줘야 하는 l, r 구간의 수가 최대 N/(r'-l'+1)이므로, Harmonic Lemma에 의해 총 업데이트 횟수가 O(N^2logN)이 된다.

이렇게 하면 O(N^2logN)이 되고, 만점이 나온다.

BOJ 21853 도로 폐쇄

DP[i][k]를 i의 서브트리에서 모든 노드의 차수를 k 이하로 만드는 최소 비용(i와 i의 부모 잇는 간선 제거 x)라 하고,

EP[i][k]를 i의 서브트리에서 모든 노드의 차수를 k 이하로 만드는 최소 비용(i와 i의 부모 잇는 간선 제거 o)라고 하자.

이는 O(N^2logN)으로 잘 계산해줄 수 있다.

이 때 하나의 k에 대해 답을 계산할 때 고려해야 하는 노드의 수는 최대 N/k개이므로 트리를 잘 압축해주면 Harmonic Lemma에 의해 O(Nlog^2N)에 답을 계산할 수 있다.

구현이 좀 귀찮은 것 같다.

BOJ 24943 Sightseeing in Kyoto

아름다운 그리디 풀이로 풀린다.

우선 2x2에서 문제를 풀자.

A1+B2>=A2+B1이라면 한쪽 방향을 제거할 수 있다.

이 조건을 A2-A1<=B2-B1으로 변형하자.

이제 모든 Ai, Bi의 인접한 차이 중 최대인 것을 일반성을 잃지 않고 Ai, Ai+1이라 하자.

이 때 Ai+1은 제거해줘도 무방하다는 것을 알 수 있다.

이제 Ai, Ai+2를 합쳐주고, 다시 제거하는 과정을 반복해주면 답을 구할 수 있다.

1/29(수) - 10일차

설날이라 따로 셋을 돌지는 않고, 전에 풀다가 못 푼 문제들을 업솔빙했다.

BOJ 32264 Tree

41점까지는 큰작으로 잘 풀면 되는데, 만점 풀이와 별로 상관은 없다.

W[i]<=1인 섭테가 가장 만점 풀이와 관련되어 있으므로 이 섭테를 먼저 풀어보자.

W[i]=1인 노드끼리 합쳐서 컴포넌트를 만들자. 이 컴포넌트의 리프의 수를 x라고 하고, 이 컴포넌트에 연결된 W[i]=0인 노드의 수를 y라고 하자.

그러면 이 컴포넌트에 대한 답은 xL+max((x+y)L-R, 0)이 된다.

이를 누적 합으로 잘 저장해두면 L, R이 주어질 때 이분탐색으로 답을 구할 수 있다.

만점 풀이에서 이 풀이를 사용한다.

결론부터 말하자면, 답은 W[i]>=x일 때 W'[i]=1, W[i]<x일 때 W'[i]=0으로 한 뒤 W'에 대해 답을 구하고, 이를 모든 x에 대해 합친 값이다.

바보 자물쇠 문제와 비슷한 직관으로 생각할 수 있다.

사실 저게 왜 되는지 완전히 받아들이지는 못했고, 그냥 그렇구나 정도로 넘어가긴 했다.

이를 계산하는 것은 W[i]<=1인 섭테의 풀이에 유니온 파인드를 결합하면 된다.

BOJ 32074 점수 경주

안타까운 문제이다.

풀이는 주어진 트리에서 Centroid Decomposition을 한 뒤 u->v의 경로를 u->c의 경로와 c->v의 경로로 나눠서 잘 풀어주면 된다.

구현이 생각보다는 덜 복잡하다.

시간 제한도 널널해서 상수 이슈로 고생하지는 않았다.

BOJ 20065 Highway Tolls

51점까지는 간단하게 풀 수 있다.

주어진 그래프가 트리이므로 이분탐색으로 S-T 경로에 포함되는 간선을 하나만 찾고, 그 간선을 기준으로 좌우에서 풀어주면 되는데, 이 또한 이분탐색으로 가능하므로 약 3logN에 문제를 해결할 수 있다.

만점 풀이는 생각보다 트리에서의 풀이와 매우 유사하다.

우선 이분탐색으로 S-T의 최단경로에 포함되는 간선을 하나만 찾는다. 이는 간선 집합에서 prefix에 1을 칠하고 쿼리를 날려서 최단경로가 달라지는 최초의 간선을 이분 탐색으로 찾으면 된다.

이 간선을 u-v라 하고, S-...-u-v-...-T로 S-T 최단경로가 구성된다고 생각하자.

이 때 S부터 u까지 거리가 T부터 u까지 거리보다 무조건 작고, v에 대해서도 유사하게 성립한다.

즉, u에서부터와 v에서부터의 거리로 S, T의 후보를 나눌 수 있다.

이제 u와 v에서부터 각각 BFS 트리를 구성하자.

S, T를 각각 이분탐색으로 찾을 것인데, BFS 트리를 구하고 거리순으로 정렬한 뒤 prefix에 있는 정점과 나머지 정점 사이의 간선에 1을 칠하고 쿼리를 날리면 S가 그 prefix에 있는지 아닌지를 알아낼 수 있음을 이용하면 된다.

최종적으로 트리에서의 풀이와 유사하게 약 3logN번의 쿼리로 답을 알아낼 수 있다.

1/30(목) - 11일차

오늘은 셋을 돌지는 않고 웰논 다이아를 풀었다.

BOJ 4011 기름 파기

겹치지 않는 세 개의 정사각형은 무조건 두 개의 가로선으로 나뉘거나, 두 개의 세로선으로 나뉘거나, 한 점에서 그은 하나의 직선과 하나의 반직선으로 나뉜다.

각 경우를 DP로 잘 계산해주면 된다.

BOJ 9522 직선 게임

일단 상황을 이분 그래프로 모델링할 수 있다.

여러 가지 이분 그래프에 대해 답을 계산해보면 대충 감을 얻을 수 있다.

이 이분그래프에서 완전매칭이 존재한다면 무조건 후공이 이기고, 그렇지 않다면 무조건 선공이 이긴다.

왜 되는지 증명은 잘 모르겠다.

1/31(금) - 12일차

24486, 24261, 21852, 27934로 이루어진 셋을 돌았다.

BOJ 24261 Same Sum Subsequences

앞에서부터 투 포인터로 계산해주면 비둘기집 원리에 의해 대충 성립한다.

사실 적당히 찍어서 풀었는데 맞았다.

BOJ 27973 마계안암

가중치가 0인 간선을 SCC로 묶고 위상정렬하면서 DP를 돌려주면 된다.

2/1(토) - 13일차

BOJ 32008 Train

APIO 때 못 풀었던 문제라 전부터 업솔빙을 하고 싶었는데, 이번 기회에 업솔빙을 해보았다.

일단 간선의 시작 시간을 기준으로 정렬해서 다음과 같은 연산을 잘 처리하면 된다.

1. 한 정점에서 현재 시점에서 최적해 구하기

2. 한 정점에서 값 업데이트하기

DP 식을 잘 세워 보면 Monotone Queue Optimization으로 최적화 가능한 형태임을 알 수 있다.

그래서 리차오를 짜거나 Monotone Queue Optimization을 하면 되는데, 나는 후자를 택했다.

이 때 알아야 하는 값 중 하나가 구간에 완전히 포함되는 L, R의 수이므로 PST를 사용해서 계산해주었다.

2/3(월) - 14일차

BOJ 21852 밀림 점프

적당히 그리디한 아이디어로 접근하면 희소 테이블로 풀 수 있다.

나는 카르테시안 트리로 접근해서 말린 것 같다.

2/4(화) - 15일차

13307, 17698, 24485, 16782로 이루어진 셋을 돌았다.

BOJ 24485 Minimizing Haybales

위상정렬을 세그먼트 트리를 활용해 최적화하는 문제이다.

각 수에 대해 그 수의 초기 indegree는 세그먼트 트리를 통해 구할 수 있다.

위상정렬에서 어떤 수가 제거될 때 줄어드는 indegree는 그 수와 차이가 K 초과 나는 모든 수들에서 1씩 줄여주면 된다.

(그 수의 앞에 있는 수는 이미 K 이하로 차이나므로 영향을 받지 않는다.)

BOJ 16782 Amusement Park

주어진 그래프에서 DFS 트리를 만들고 그 간선만 남긴다.

이제 DFS를 하면서 진행할 것이다.

DFS를 한 결과 인접한 정점이 60개 이상인 경우 그 앞의 60개만 X의 0~59번째 비트로 값을 써주고 이 정점들을 제거한다.

인접한 정점이 60개 미만인 경우 이 정점들 중 인접한 60개 묶음을 보면서 가장 먼 정점의 값부터 가까운 정점부터 써주면 된다.

이렇게 하면 항상 인접한 60개로 0~59번째 비트를 확인할 수 있다.

2/5(수) - 16일차

10071, 28025, 18842, 31817로 이루어진 셋을 돌았다.

BOJ 28025 Pareidolia

우선 O(NQ) DP 풀이를 떠올릴 수 있다.

6 * N DP를 계산하면 된다.

이를 금광 세그로 잘 최적화하면 O(QlogN)에 풀 수 있다.

BOJ 10071 Game

존재한다고 답한 간선들로 Union-Find를 해주면서 진행하자.

현재 a, b를 잇는 간선이 있는지에 대한 쿼리가 들어왔고, a, b의 컴포넌트에는 각각 x, y개의 정점이 존재한다고 하자.

a, b 컴포넌트가 같다면 아무렇게나 답하면 된다.

a, b 컴포넌트가 다르다면 두 컴포넌트를 잇는 간선 중 마지막 간선일 때만 1, 아니면 0을 반환하면 된다.

BOJ 18842 Chameleon's Love

두 카멜레온의 색이 같거나 둘 중 하나가 좋아하는 관계라면 간선을 잇자.

간선은 총 3N개 존재할 것이다.

카멜레온을 순서대로 보면서 모든 간선을 확인할 것이다.

우선 지금까지 나온 카멜레온의 그래프는 이분 그래프이므로, 0, 1로 색칠할 수 있다.

0으로 색칠된 카멜레온의 부분집합과 새로운 카멜레온의 합집합으로 쿼리를 날렸을 때 그 집합의 크기가 나온다면 그 부분집합과는 간선이 있고, 그렇지 않다면 간선이 아니다.

따라서 이분탐색으로 간선을 다 찾아줄 수 있다.

간선을 찾았을 때 이 간선이 같은 색에 의한 간선인지 확인하는 것은 다음과 같이 할 수 있다.

a, b가 같은 색인지 확인하기 위해 Query({a, b})와 Query(U-{a, b})를 하면 된다.

2/6(목) - 17일차

14422, 10862, 31074, 31056으로 이루어진 셋을 돌았다.

BOJ 31074 싱글 플레이어 게임

전체 구간에 한 번의 쿼리를 날려서 전체 구간에서 1, 2, 3, 4의 개수를 순서 없이 알아낼 수 있다.(1번)

logN번의 쿼리를 날려서 첫 번째 3의 위치를 찾을 수 있다. (10 + 1 = 11번)

이 때, diff가 아닌 count로 쿼리를 날리면 첫번째 3 왼쪽의 1, 2 개수를 순서 없이 알아낼 수 있다.

첫번째 3의 위치를 p라고 하고, [2, p-1]에서 쿼리를 날리자. 그러면 첫번째 3 왼쪽의 1, 2 개수를 각각 알아낼 수 있다. (11 + 1 = 12번)

그 1, 2의 개수를 a, b라고 하자.

[2, N]에서 쿼리를 날리자. 그러면 전체 구간에서 1의 개수를 알아낼 수 있다.(12 + 1 = 13번)

[a+2, N]에서 쿼리를 날리자. 그러면 전체 구간에서 2의 개수를 알아낼 수 있다.(13+1 = 14번)

[a+b+2, N]에서 쿼리를 날리자. 그러면 전체 구간에서 3의 개수를 알아낼 수 있고, N에서 1, 2, 3의 개수를 빼 4의 개수도 알아낼 수 있다.(14 + 1 = 15번)

처음에 위의 진하게 처리한 부분을 발견하지 못해 15번을 맞추기 위해 열심히 뇌절했는데, 그 풀이를 잘 활용하면 어쩌면 14번의 쿼리로 답을 찾는 것도 가능해보인다.

BOJ 14422 Soccer

기본적으로 다익스트라를 돌릴 것이다.

(i, j, d)를 d>0인 경우 (i, j)에서 사람 없이 공이 d 방향으로 이동하고 있다 / d=0인 경우 사람과 공이 있다

로 상태를 정의할 것이다.

(i, j, d) <-> (i, j+1, d) 가중치 a (d가 좌우 방향인 경우)

(i, j, d) <-> (i+1, j, d) 가중치 a (d가 상하 방향인 경우)

(i, j, d) -> (i, j, 0) 가중치 (i, j)에서 가장 가까운 선수까지 거리 (d>0)

(i, j, 0) -> (i, j, d) 가중치 b (d>0)

위와 같이 그래프를 구성하면 된다.

이 때 들 수 있는 의문은 한 선수가 어딘가에서 공을 받고 다시 찬 다음 다른 위치에서 받는 경우, 실제로는 답이 될리가 없지만 계산 과정에서 그 선수의 이동 거리가 누락되어 답이 더 작게 나올 수는 없냐는 것이다.

그런데 그런 경우는 존재하지 않는 것 같다.

2/7(금) - 18일차

31818, 21848, 17677, 5819로 이루어진 셋을 돌았다.

BOJ 31818 Discount Event

u부터 v까지의 경로를 0으로 바꾸고 지름을 찾아야 한다.

경우를 잘 나누고 7가지 DP 값을 관리해서 풀었다.

구현 디테일이 복잡한데, 잘 풀어주면 된다.

BOJ 5819 열대 식물원

정점을 두 개로 분할해서 이전 간선이 가장 아름다운 간선이었던 정점과 그렇지 않은 정점을 만들자.

이 그래프는 functional graph이므로 간단하게 해결할 수 있다.

BOJ 17677 케이크 3

우선 C를 기준으로 정렬하자.

l, r을 양끝으로 하는 최댓값을 f(l, r)이라 하면, f(l, r)=V[l]+V[r]+(l+1~r-1의 V 값 중 가장 큰 M-2개의 합)-2(C[r]-C[l])이 된다.

이 때, 하나의 r에 대해 f(l, r)이 최대가 되는 l을 opt(r)이라 할 때, opt(r)은 단조 증가함을 다음과 같이 증명할 수 있다.

opt(r)>opt(r+1)이라고 가정하자.

opt의 정의에 의해 f(opt(r+1), r)<f(opt(r), r)이다.

또한 f(opt(r+1), r+1)-f(opt(r+1), r)<f(opt(r), r+1)-f(opt(r)-r)이 성립한다.

(l, r에 대한 항은 상수이므로 결국 l+1~r-1의 V 값 중 가장 큰 M-2개의 합의 변화를 보면 되는데, 이는 opt(r+1)~r-1에서 opt(r+1)~r까지의 변화보다 opt(r)~r-1에서 opt(r)~r까지의 변화가 더 크기 때문이다.)

두 부등식을 더하면 f(opt(r+1), r+1)<f(opt(r), r+1)이므로 opt의 정의에 모순이다.

따라서 DnC optimization을 적용할 수 있는 형태가 된다.

f(l, r)을 계산하는 것은 PST로 잘 처리해줄 수 있다.

BOJ 31817 Two Histograms

경우를 나눠서 DP를 잘 하면 된다.

잘 설명된 블로그들이 있으니 풀이는 적지 않겠다.

나는 코드를 디버깅하느라 오랫동안 고생했는데, 굉장히 잡기 힘든 버그들이 있어서 N^2 코드를 돌리고 랜덤 테케를 열심히 만들면서 디버깅했다.

인생에서 손에 꼽을 만한 버그였던 것 같다.

2/8(토) - 19일차

BOJ 24486 Counting Haybales

여러가지 관찰을 통해 풀 수 있는 재밌는 문제였던 것 같다.

우선 같은 수끼리의 위치 관계는 바뀔 수 없다는 것을 알 수 있다.

이 관찰을 발전시키기 위해 h[i]<=3인 서브태스크가 도움이 된다.

이 서브태스크에서는 2의 위치는 자유롭게 이동할 수 있고, 나머지는 이동할 수 없어 답이 nC(2의 개수)가 된다.

이를 통해 다음과 같은 관찰을 할 수 있다.

관찰. 홀수끼리, 짝수끼리의 위치 관계는 바뀔 수 없다.

위 관찰은 어쩌면 당연할 수 있지만, 이를 통해 문제를 해결할 수 있다.

DP[i][j]를 홀수를 i번째 수까지 사용했고, 짝수를 j번째 수까지 사용했을 때 최소 비용으로 정의하면 잘 계산해줄 수 있다.

BOJ 10862 DOSTAVA

난이도에 비해 레이팅이 과대평가되었다고 생각한다.

각 (x, y, t)별로 조건을 생각해보면 (x, y)에서부터의 거리가 t 미만인 지점에 식당이 없고, (x, y)에서부터의 거리가 t인 지점 중 최소 하나에 식당이 있는 것이다.

이는 세그먼트 트리 + 스위핑으로 잘 해결해줄 수 있다.

이 때 두 가지 대각선 방향을 고려해야 하고, 홀짝을 나눠서 생각해야 하는데, 이 부분 구현을 잘 해줘야 한다.

2/9(일) - 20일차

BOJ 13307 레이저 센서

신기한 문제였다.

우선 답이 -1인 경우가 없음을 증명할 수 있다.

모든 매칭 중 선분의 길이 합이 최소인 매칭을 생각하면, 교차하는 선분이 있으면 선분의 길이 합이 더 작은 매칭이 존재하여 모순이 되기 때문에, 선분의 길이 합이 최소인 매칭은 항상 답이 된다.

따라서 가능한 매칭을 찾기만 하면 된다.

이는 분할정복으로 잘 해결할 수 있다.

기본적인 아이디어는 주어진 점들을 파란점과 빨간점의 개수 비율이 1:2이고, 서로 영향을 주지 않는 부분들로 나누는 과정을 반복하는 것이다. 구체적으로는 다음과 같이 할 수 있다.

현재 주어진 점들에서 Convex Hull을 구하자.

i) Convex Hull에 파란 점이 있는 경우

그 점을 기준으로 모든 점을 각도 정렬한다. 그러면 Convex Hull에서 인접한 두 점으로 시작하고 끝나게 만들 수 있을 것이다.

파란점을 +2, 빨간 점을 -1로 생각하면 +2로 시작해서 점수를 더해 나가면 끝나는 시점에 점수가 0이 될 것이다.

따라서 그 사이에 점수가 1 또는 0인 시점이 무조건 존재할 것이고, 그 시점은 빨간 점이 추가되는 시점일 것이다.

파란 점과 두 시점의 빨간 점을 연결하고, 각도로 정렬한 상태에서 세 부분으로 쪼개서 분할정복을 하면 된다.

ii) Convex Hull에 파란 점이 없는 경우

Convex Hull이 빨간 점으로만 이루어져 있다.

위 경우와 비슷하게 한 빨간 점에서 점수 -1에서 시작해 각도 정렬을 하고 점수를 더해가며 0인 시점을 기준으로 둘로 분할한다. (연결을 하지는 않는다.)

이 때 점수가 0이 되는 시점이 마지막을 제외하고 존재하지 않는 경우가 있는데, 그 경우 각도를 반대 방향으로 정렬하면 점수가 0인 시점이 무조건 생긴다.

BOJ 17698 Long Distance Coach

문제 상황이 매우 복잡하여 이해하기 힘들다.

나도 문제 조건을 하나 잘못 읽어서 헤맸다.

DP 식을 M에 대해서 구성할 수 있고, 이를 뒤에서부터 업데이트하면 CHT로 최적화할 수 있는 형태가 되어 리차오 트리를 쓰면 맞는다.

대략적인 DP 형태는 DP[i]=Min(DP[i+1]+(i에 대한 함수), Min(DP[j+1]+(i~j를 중간에 내리게 하는 비용)))의 형태이다.

long long을 넘어갈거 같아서 __int128을 써서 맞았다.

2/10(월) - 21일차

29204, 24068, 19558, 17191로 이루어진 셋을 돌았다.

BOJ 19558 Joker

모든 l에 대해 l번째 간선부터 r번째 간선까지를 모두 제거했을 때 홀수 사이클이 남아 있는 최대 r을 관리한다고 하자.

이런 r을 opt(l)이라고 하면, opt(l)은 증가하는 값임을 알 수 있다.

따라서 DnC 최적화를 적용해 문제를 해결할 수 있다.

l이 [s, e]에 포함되고, r이 [s2, e2]에 포함될 때의 최적해를 구하는 함수를 f(s, e, s2, e2)라고 하자.

f(s, e, s2, e2)를 호출하기 전에 [1, s-1]과 [e2+1, M]의 간선들이 이미 연결된 상태를 만들어 놓으면 m=(s+e)/2에 대해 opt(m)을 Union Find로 구할 수 있다.

f(s, e, s2, e2)에서 다음 함수를 호출하기 전에 연결해야 할 간선들을 연결하면 되는데, 이는 Roll-Back Union Find로 해결할 수 있다.

홀수 사이클 판별은 각 정점별로 색을 관리하면서 할 수 있다.

한 컴포넌트의 두 정점을 연결할 때 색이 같다면 홀수 사이클이 생기고, 서로 다른 두 컴포넌트의 정점을 연결할 때에는 홀수 사이클이 생기지는 않고 연결하는 두 정점의 색이 같다면 둘 중 한 컴포넌트의 모든 정점의 색을 뒤집어주면 된다.

BOJ 24068 XCopy

풀이가 매력적이라고 생각해 자세히 적어보겠다.

 

우선 N, M이 2의 거듭제곱인 경우는 0에서 시작해서 다음 비트를 더하고 원래 배열을 뒤집어서 붙이는 과정을 반복해 해결할 수 있다.

그 다음으로 해결해야 하는 경우는 N=1인 경우이다.

N=1인 경우 M을 2의 거듭제곱의 합으로 나타낸 뒤, 각 거듭제곱 별로 위 방법으로 그 크기의 그레이 코드를 만든다.

이 때 만들어지는 2의 거듭제곱 크기의 그레이 코드는 cyclic하게 shift해도 그레이 코드임이 유지된다는 것을 관찰하면 된다.

예를 들어 M=14=1110(2)인 경우, M=8+4+2로 나타낼 수 있으므로, 다음과 같이 거듭제곱 그레이 코드를 만들 수 있다.

[0, 1, 3, 2, 6, 7, 5, 4], [0, 1, 3, 2], [0, 1]

이 그레이 코드들에 적절히 값을 더해서 0부터 M-1까지의 수로 만든다. 다음과 같다.

[0, 1, 3, 2, 6, 7, 5, 4], [8, 9, 11, 10], [12, 13]

이제 두 그레이 코드의 끝 값이 한 비트 차이나도록 만들 것이다. 이는 오른쪽부터 cyclic하게 shift하는 과정을 반복해 만들 수 있다.

12와 한 비트 차이 나는 수는 [8, 11]에서 8로 유일하다. 따라서 8이 가장 오른쪽으로 오도록 한다.

[0, 1, 3, 2, 6, 7, 5, 4], [9, 11, 10, 8], [12, 13]

9와 한 비트 차이 나는 수는 1로 유일하다. 따라서 1이 가장 오른쪽으로 오도록 한다.

[3, 2, 6, 7, 5, 4, 0, 1], [9, 11, 10, 8], [12, 13]

짜잔! 0~13으로 이루어진 길이 14의 그레이 코드를 완성했다!

이제 N, M의 조건이 없는 일반적인 경우의 문제를 해결해보자.

기본적으로 [0, N-1]의 그레이 코드와 [0, M-1]의 그레이 코드를 만들어서 두 코드를 합쳐주는 느낌으로 할 것이다.

[0, N-1]의 그레이 코드를 {a[i]}라고 하고, [0, M-1]의 그레이 코드를 {b[i]}라고 하면, (i, j)의 값을 a[i], b[j]의 비트를 적절히 조합해 만들 수 있다.

이 때 a[i], b[j]의 비트를 조합하는 방법에 따라 2차원 배열 안의 값 중 최댓값이 달라질 수 있다.

따라서 이를 DP로 구하고, 역추적한 뒤 비트를 조합해서 출력하면 된다.

2/11(화) - 22일차

18779, 25443, 27461, 29205로 이루어진 셋을 돌았다.

BOJ 27461 Bounded Spanning Tree

Dumae, 보급과 매우 유사하다.

위 문제는 DAG에서 a에서 b로 가는 간선이 있을 때, L[b]=max(L[b], L[a]+1), R[a]=min(R[a], R[b]-1)을 처리해준 뒤에 그리디하게 배정해주면 된다.

이 문제는 이를 트리의 경로 상에서 풀어야 하는데, LCA와 큰작으로 잘 처리해주면 된다.

BOJ 18799 Help Yourself

L을 기준으로 정렬해서 DP 식을 잘 세울 수 있다.

이 때 K제곱을 해야 하므로 0제곱의 합, ..., K제곱의 합을 모두 관리하면서 이항정리로 계산해줄 수 있다.

이를 느리게 갱신되는 세그먼트 트리로 빠르게 처리하면 된다.

2/12(수) - 23일차

셋을 돌지는 않고, 전에 못 푼 문제들을 업솔빙했다.

BOJ 29204 KSA에서 숨바꼭질

처음에 v 정점에 리모콘을 사용했고, k라는 결과를 받았으면 찾고자 하는 정점은 v에서부터 k만큼 떨어져 있음을 알 수 있다.

이제 v를 루트로 트리를 봤을 때, 한 정점에 리모콘을 날릴 때마다 그 정점과 찾고자 하는 정점의 lca를 알게 된다.

따라서 dp[i]를 i의 서브트리에서 정점 찾는데 필요한 최소 쿼리 횟수라고 하면, dp[i]=max(dp[v[j]]+j)로 계산할 수 있다.

(단, v[0], ..., v[k]는 i의 자식들이고, dp[v[j]]는 내림차순 정렬되어있다.)

이를 모든 v, k에 대해 따로 풀면 O(N^3logN)이고, dp 계산에 사용되는 서브트리 종류가 최대 N개이므로 이를 O(N^2logN)으로 최적화할 수 있다.

BOJ 29205 마라톤

개인적으로 정말 어려웠다.

일단 유효한 경로를 생각해보면, 1에서 v까지 이동하고, v에서 가장 가까운 정점까지 왔다갔다를 반복하고, v에서 다시 N으로 이동하는 경로 뿐임을 알 수 있다.

이 관찰이 가장 중요하고, 나머지는 1, N에서 v까지의 거리를 홀짝에 따라 구하고 CHT로 적당히 처리할 수 있다.

2/13(목) - 24일차

15867, 21846, 23871, 27473으로 이루어진 셋을 돌았다.

BOJ 23871 HILO

간단한 DP 식으로 풀 수 있는데 엄청 뇌절해서 풀었다.

최종 풀이는 깔끔하긴 한데, 귀찮아서 적지 않겠다.

BOJ 25443 수천개의 섬

최근에 푼 문제들 중 가장 아름다운 문제였던 것 같다.

풀이는 한 줄로 거의 끝나는데, outdegree가 0인 정점을 제거하는 과정을 반복하면 답을 쉽게 찾을 수 있다.

그 이후는 적당히 풀 수 있다.

2/14(금) - 25일차

14523, 15777, 17632, 31968로 이루어진 셋을 돌았다.

BOJ 15777 Xtreme NP-Hard Problem?!

K>=N이면 답이 -1이다.

따라서 K<N인 경우만 풀면 되고, 이 경우 K<=5 또는 M<=5일 것이다.

M<=5는 그냥 브루트 포스를 하면 된다.

K<=5는 밋 인더 미들로 적당히 비비면 된다.

BOJ 14523 Switch Grass

셋 시간 중에 풀었다.

일반적인 무방향 그래프에서 각 정점에 색이 있고, 서로 다른 색으로 칠해진 두 정점 사이의 거리의 최솟값을 구해야 한다.

이 때 쿼리로 한 정점의 색이 바뀔 때마다 답을 구해야 한다.

우선 굳이 경로를 고려할 필요 없이, 간선 하나씩만 고려해도 됨을 관찰할 수 있다.

이렇게 하면 모든 정점의 차수가 작을 때는 풀리겠지만, 차수가 큰 정점이 있을 때는 쉽지 않다.

이 다음에는 주어진 그래프의 최소 스패닝 트리만 고려하면 된다는 사실을 관찰할 수 있다.

최소 스패닝 트리에 포함되지 않는 간선에서 최솟값이 나왔다면 더 짧은 최소 스패닝 트리가 존재하기 때문이다.

따라서 최소 스패닝 트리의 간선들만 고려하면 되고, 이는 각 정점별로 자식 수만큼 세그먼트 트리를 관리하면 풀린다.

BOJ 21846 Inside Information

전에 셋 돌 때 시간이 없어서 못 푼 문제를 다시 풀어보았다.

로그 세제곱으로 뇌절해서 풀었는데, 로그 제곱의 쉬운 풀이를 AC를 받은 후에 발견하고 말았다.

2/15(토) - 26일차

셋을 돌지 않았다.

BOJ 27473 판 뒤집기 게임

풀이가 매우 신기하다.

이런거 어떻게 푸는지 모르겠다.

2/16(일) - 27일차

10756, 18847, 28030, 31071로 이루어진 셋을 돌았다.

BOJ 10756 편식

주어진 점들의 볼록껍질을 구하고 투 포인터로 대충 풀어주면 된다.

BOJ 28030 Tree Merging

엄청 뇌절해서 풀었다.

대충 merge를 하기 전/후의 트리를 비교하면서 풀면 된다.

BOJ 31071 사진 촬영

N<=100은 A->B, B->A 순서를 2^K로 정하고, 트리 DP를 Exchange Argument로 잘 돌려주면 된다.

N이 커져도 유의미한 정점은 몇 개 없기 때문에 트리를 압축해서 풀면 똑같이 풀 수 있다.

나는 구현에서 꽤나 고생했다.

BOJ 18847 Stray Cat

일자일 때가 가장 어려운 경우이다.

일자일 때는 010011을 반복해서 쓰면 아무 방향이나 3번 이동해서 5개의 연속한 문자를 알아낼 수 있고, 현재 방향이 맞는 방향인지 틀린 방향인지를 알아내서 방향을 정하고 쭉 올라가면 된다.

트리일 때도 비슷하게 풀리는데, 차수가 3 이상인 정점에 도착하면 방향이 바로 결정할 수 있고, 그렇지 않으면 위의 일자 풀이를 적용하면 된다.

2/17(월) - 28일차

15842, 18259, 27355, 31735로 이루어진 셋을 돌았다.

BOJ 18259 Greedy Pie Eaters

DP[l][r]을 l~r에서 최댓값으로 정의하면

DP[l][r]=max(DP[l+1][r], DP[l][r-1], DP[l][k-1]+DP[k+1][r]+(k를 포함하고 [l, r] 구간에 완전히 포함되는 소의 가중치의 최댓값))으로 계산할 수 있다.

이 때 진하게 색칠한 부분은 전처리로 O(N^3)에 계산할 수 있고, 전체 DP 식도 O(N^3)에 계산할 수 있다.

BOJ 15842 Koala Game

1. minValue : 1, 0, ..., 0으로 쿼리를 날리면 된다.

2. maxValue : 처음에 1, 1, ..., 1으로 쿼리를 날리면 가장 큰 절반을 알 수 있다. 그 절반에 2를 넣고 나머지에 0을 넣어서 쿼리를 날리면 가장 큰 몇개를 또 알 수 있다. 이를 반복하면 가장 큰 원소를 알 수 있다.

3. greaterValue : x, x를 넣어서 쿼리를 날리는데, x를 이분 탐색하면 된다.(나는 이분 탐색할 생각을 못해서 각 x에 대해 일일히 계산해서 풀었다.)

4. allValue : 처음에 minValue를 날리면 최솟값의 위치를 알 수 있다. [l, r] 구간에 x[1], ..., x[r-l+1]이 들어간다는 것을 알고 있다고 가정하자. 이 때 한 번의 쿼리로 이 구간을 두 개의 구간으로 나눈다면 이 과정을 반복해 구간을 모두 크기가 1인 구간으로 나눠서 모든 값을 알 수 있다. 이는 x[1], ..., x[r-l+1]에 적당한 같은 수 y를 넣고 나머지에 0을 넣어서 쿼리를 날림으로서 해결할 수 있다. 이러한 y는 무조건 존재한다고 믿고 짜니까 맞았다.

BOJ 31735 Escape Route 2

분명 O(Nsqrt(QlogN))을 짰는데 계속 시간 초과가 나서 같은 시간 복잡도의 더 효율적인 코드를 짜서 맞았다.

기본적인 아이디어는 가능한 모든 시작점에서 시작해서 희소 테이블로 최솟값을 구하되, 시작점이 sqrtN개 이상인 경우에는 따로 전처리를 하는 것이다.

사실 생각해보면 시작점이 sqrtN개 이상인 지점은 최대 sqrtN개이므로 그냥 그런 정점들에서 다른 모든 정점들까지 최소 거리를 전처리해줘도 된다.

2/18(화) - 29일차

오늘은 웰논 다4를 좀 풀고 지금까지 쌓인 문제들을 업솔빙했다.

BOJ 10637 Minimum Spanning Tree

일단 MST를 하나 구한다.

MST에 포함되지 않는 간선을 지우면 답은 유지된다.

MST의 간선을 하나 지우면 그 간선을 삭제했을 때 나눠지는 두 컴포넌트에 대해 두 컴포넌트를 잇는 다른 간선 중 최솟값으로 대체된다.

이는 LCA + 큰작으로 계산해줄 수 있다.

BOJ 20177 Stock Analysis

모든 (l, r)에 대해 A[l]+...+A[r]을 기준으로 정렬하고 쿼리도 U를 기준으로 정렬해서 오프라인 쿼리로 처리한다.

(l, r) 위치에 A[l]+...+A[r]을 업데이트하는 쿼리와 (l>=L, r<=R)인 (l, r)에 대해 A[l]+...+A[r]의 최댓값을 구하는 쿼리를 처리하면 되는데, 이는 2차원 펜윅 트리로 할 수 있다.

BOJ 26613 수열과 구간과 구간과 구간과 쿼리

구간 (l+1, r)에 대해 답이 t 이상일 조건은 S[r]-S[l]-t*(r-l)>=0인 것이다.

따라서 이분탐색을 하면서 답이 t 이상인 l, r이 존재하는지를 판단해주면 된다.

S[r]-tr이 최대인 r을 [c, d] 범위에서 찾고, -S[l]+tl이 최대인 l을 [a-1, b-1] 범위에서 찾으면 되는데, 이는 cht 세그먼트 트리로 찾을 수 있다.

BOJ 10745 Censoring

해시로 주어진 단어들을 삭제해주면 된다.

이 때 주어진 단어들의 서로 다른 길이의 가짓수가 최대 sqrtN개이므로 길이별로 해시 값을 확인하면 된다.

BOJ 1608 스타 대회

좀 재밌었다.

일단 정점들을 SCC로 묶었을 때, 같은 SCC에 포함된 두 정점의 결과는 같다.

따라서 DAG로 만들 수 있다.

이 때 SCC a, b가 있을 때 a의 모든 정점에서 b의 모든 정점까지 간선이 존재할 때만 a에서 b로 간선을 잇자.

indegree=0인 SCC는 무조건 우승할 수 있다. 이 SCC들을 우승 후보에 넣자.

우승후보 x에 대해 x에서 y로 직접적으로 가는 간선이 없는 y는 우승 후보가 된다. 이를 반복해서 우승 후보를 모두 구할 수 있다.

BOJ 27355 Paths

풀이가 굉장히 신기한 문제인 것 같다.

그리디하게 하면 된다는 관찰까지는 했는데, 이를 빠르게 구하는 방법을 떠올리지 못했다.

일단 루트를 고정하고 문제를 풀어보자.

우선 루트에서 가장 먼 리프부터 고르고, 그 정점까지의 간선의 가중치를 0으로 만드는 과정을 K번 반복하면 답을 구할 수 있다는 것을 알 수 있다.

따라서 그 경로들을 잘 구해주기만 하면 된다.

리프 x를 고른 시점에서 x까지의 유효한 경로를 a[x]부터 x까지라고 하고, down[v]를 v의 서브트리에서 v에서 가장 먼 리프의 번호라고 하자.

그러면 a[x]는 (down[v]!=x인 가장 낮은 x의 조상 v, 또는 그런 v가 없는 경우 루트)가 된다.

따라서 a[x]를 모든 x별로 빠르게 구할 수 있고, 모든 경로의 길이를 pq에 넣고 가장 큰 K개를 뽑으면 답이 된다.

루트를 바꾸는 과정도 생각보다 그리 어렵지 않다.

우선 up[v]를 v의 서브트리의 여집합에서 v에서 가장 먼 리프의 번호라고 하자.

그러면 루트가 r에서 t로 바뀌었을 때(t는 r의 자식), a[x]가 바뀌는 리프의 개수는 down[t], up[r]로 2개이다.

따라서 두 개의 값만 바꾸고 가장 큰 K개의 합을 구하면 된다.

이는 셋 2개를 관리하는 방법으로 간단하게 해결할 수 있다.

BOJ 31968 Jobs

적당히 큰작으로 풀 수 있다.

초기에 a 이상의 자본을 가지고 있었을 때 b만큼의 수익을 얻을 수 있는 (a, b) 쌍을 관리한다고 하자.

한 노드에서는 그 노드의 자식들의 (a, b) 값을 큰작으로 합쳐준다.

이 때 s[i]>0이라면 그냥 (0, s[i])를 추가하면 된다.

s[i]<0이라면 (a, b)를 적당히 제거하고 다시 추가해주면 된다.

2/19(수) - 30일차

17188, 27553, 28059, 31072로 이루어진 셋을 돌았다.

BOJ 17188 Olympiads

Robotic Cow Herds와 비슷하게 큰 것부터 pq에 넣고 하나씩 바꾸면서 관리하는 방식으로 풀면 풀린다.

이런 테크닉을 Fracturing Search라고 한다는 것 같다.

BOJ 28059 Remix

a[i]의 최댓값에서 나머지로 만들 수 있는 수의 최솟값을 빼면 된다.

이 최솟값은 각 a[i]에 +1, -1, 0을 적당히 배정해서 a[i]와 배정된 수의 곱의 합의 절댓값의 최솟값이 된다.

그러나 N이 커서 이를 Naive하게 하면 O(N*max(a[i]))가 된다.

하지만 생각해보면 N이 약 30 정도보다 크다면 0을 무조건 만들 수 있다는 것을 알 수 있다.

a[1], ..., a[30]에 0, 1을 배정한 수의 종류는 최대 30*10^5이고, 종류는 2^30가지이므로 비둘기집에 의해 무조건 중복이 생기고, 그 중복에 대해 배정된 0, 1을 서로 빼면 -1, 0, 1을 배정해 합이 0이 되게 만든 셈이 되기 때문이다.

따라서 30개만 돌려보면 된다.

+1, -1, 0을 배정한 뒤 이를 실제 해로 구성하는 것은 생각보다 간단한다.

+1이 배정된 수들의 집합을 A라고 하고, -1이 배정된 수들의 집합을 B라고 하자.

그러면 (A의 원소의 합)-(B의 원소의 합)이 현재 만들고자 하는 값이 된다.

A, B에서 원소를 하나씩 빼서 연산을 적용한 뒤, A의 원소가 더 크면 A에, 그렇지 않으면 B에 두 원소의 차를 넣으면 된다.

그러면 (A의 원소의 합)-(B의 원소의 합)이 유지되면서 A, B의 크기의 합은 감소하기 때문에 이를 반복하면 원하는 값을 얻을 수 있다.

BOJ 27553 Mana Collection

길게 적기엔 식이 많아져서 복잡한데, 대충 비트 디피 + CHT를 돌리면 된다.

주의할 점은 경로가 반드시 단순경로일 필요는 없어서, 각 정점별로 마지막 방문되는 시점만 고려한다고 생각하고, 모든 정점 사이에 (두 정점 사이의 최단경로)의 가중치를 갖는 간선을 만들어줘야 한다.

BOJ 15867 Subway

정말 어려운 문제인 것 같다.

풀이는 다른 블로그에 잘 정리되어있는데, 풀이가 왜 성립하는지 직관적으로 다가오지는 않는다.

반례를 만들려고 했을 때 잘 안 되는 것을 보아 성립하기는 하는 것 같으나, 이런 발상을 어떻게 해야 하는지는 잘 와닿지 않는다.

2/20(목) - 31일차

12752, 16012, 20105, 32045로 이루어진 셋을 돌았다.

오늘은 셋의 모든 문제를 시간 내에 해결하는 것에 성공했다!

BOJ 32045 Sprinklers

우선 답으로 이분탐색을 한다고 하고 K를 고정하자.

어떤 꽃 i에 대해, i 왼쪽의 꽃은 이미 물을 준 상태이고, i의 왼쪽의 스프링클러는 다 쓴 상태이며, i의 오른쪽에 i에 물을 줄 수 있는 스프링클러가 j, j+1, ...이 있다고 하자.

첫 번째 경우는 j가 왼쪽으로 물을 주는 경우이다. 이 경우 i는 j보다 오른쪽에 있는 첫번째 꽃으로 바뀌고, j는 j+1이 된다.

두 번째 경우는 j가 오른쪽으로, j+1이 왼쪽으로 물을 주는 경우이다. 이 경우 i는 j의 위치+K보다 오른쪽에 있는 첫 번째 꽃으로 바뀌고, j는 j+2가 된다.

그 외의 경우는 모두 위의 두 가지 경우의 하위호환임을 알 수 있고, 위 과정을 DP로 구해주면 맞는다.

구체적으로는 DP[i]를 i-1번째 꽃까지는 j-1번 스프링클러까지 사용해 모두 물을 주었고, i번째 꽃부터 마지막 꽃까지를 j번째 스프링클러로 물을 주면 되는 최소 j라고 하면 DP[i]를 O(NlogN)에 구할 수 있다.

BOJ 12752 도시들

재밌는 문제였다.

처음에 시도한 방법은 트리 상에서 생길 수 있는 K개의 정점의 위치관계를 모두 따져보는 것이었다.

그런데 이 방법을 계속 고민해보니 훨씬 쉬운 풀이가 떠올랐다.

2^K개의 정점을 새로 만들어 i번 정점은 i의 비트에 있는 정점들을 모두 모은 정점이라고 하고 다익스트라를 2^K번 돌리면 풀린다.

BOJ 16012 Elections

+1, -1로 이루어진 수열에서 앞에서부터의 부분합이 0 이상이 되고, 뒤에서부터의 부분합이 0 이상이 되도록 -1을 제거해야 하는 -1의 최소개수를 l, r 쿼리로 푸는 문제였다.

대충 직관적으로 모든 i(l<=i<r)에 대해서 ([l, i]의 누적합의 최댓값+[r, i+1]의 누적합의 최댓값)의 최댓값이 답이 된다.

이는 금광세그로 구현해줄 수 있다.

BOJ 20105 Last Supper

문제 지문이 굉장히 긴데, 쓸모 있는 말은 몇 줄 없다.

약간 넌센스 퀴즈라고 생각한다.

각 물감 별로 그 물감이 다음에 나오기 전까지 살아남는지 아닌지를 전달하면 N+K개의 비트를 통해 정보를 충분히 전달할 수 있다.

BOJ 33498 DFS Order

올해 USACO 때 못 풀었는데, 풀이가 생각보다 훨씬 간단하다.

왜 못 풀었는지는 잘 모르겠다. DP에 약한 것 같기도 하다.

BOJ 17191 Valleys

일단 최댓값이 x인 valley를 모두 구해보자.

x부터 bfs를 하면서 x 미만인 칸들은 모두 이 valley에 포함시켜야 한다.

bfs가 종료되면 이 valley에 인접한 칸들은 모두 x초과일 것이다. 즉, 이 valley로 유일하다.

이는 x가 작은 것부터 보면서 union-find로 처리할 수 있다.

그러나 문제는 hole이 생긴 valley는 답에 고려하지 않아야 한다는 것이다.

이를 해결하기 위해 모든 valley를 관리하면서 hole의 수를 관리해야 한다.

우선 생각할 수 있는 접근은 x가 큰 것부터 보면서 hole을 관리하는 것이다.

x에 따른 전체 hole의 개수만 저장을 해놓자.

이후 다시 x가 작은 것부터 보면서 union-find를 한다.

이 때 x가 추가됨으로써 바뀌는 hole의 개수는 아까 구해놓았던 (x+1에서의 hole의 개수)-(x에서의 hole의 개수) 만큼 바뀐다는 것을 알 수 있다.

전체 hole의 개수의 차이지만, 저 차이는 x에 의한 변화량만을 의미하기 때문이다.

따라서 O(N^2log*N)정도에 전체 문제를 해결할 수 있다.

2/21(금) - 32일차

따로 셋을 돌지는 않고, 그냥 문제들을 골라서 풀었다.

BOJ 13431 트리 문제

센트로이드 트리를 짜면 된다.

BOJ 12023 연세대학교 포인트 게임

13431과 같은 문제이다.

BOJ 17424 2xN 타일링과 쿼리

4x4 금광세그를 짜면 된다.

BOJ 28405 안테나 설치

스택 + 레이지 세그 DP로 풀 수 있다.

덱 DP로도 풀 수 있다는 것 같은데 잘 모르겠다.

BOJ 17962 Game on a Tree

조상-자손 관계인 모든 정점들을 간선으로 이었을 때 Perfect Matching이 존재하면 후공이, 그렇지 않다면 선공이 이긴다.

BOJ 9244 핀볼

왼쪽부터 스위핑하면서 셋을 관리하면 각 선분별로 그 선분 이후에 어디로 가는지를 알아낼 수 있다.

x에서 공이 떨어졌을 때 처음 닿는 선분부터 쭉 이동해서 마지막 선분의 좌표를 찍어주면 된다.

BOJ 17632 Colouring a rectangle

대각선의 종류를 A, B라고 하면, A의 한 대각선을 칠하지 않으려면 B에서 어떤 구간의 대각선을 모두 골라야 한다.

이는 레이지 세그 DP로 풀 수 있다.

BOJ 21848 The Short Shank; Redemption

T보다 큰 죄수 x에 대해, 그 죄수에게 영향을 줄 수 있는 가장 오른쪽 죄수를 l이라고 하면, [l+1, x]에 매트리스를 놓으면 이 죄수를 비활성화할 수 있다.

근데 생각해보면 이 구간들은 항상 교집합이 없거나 포함관계에 있다. 따라서 트리를 구성할 수 있다.

트리를 구성하면 Paths에서 루트가 고정된 문제에 해당하므로, O(NlogN)에 문제를 해결할 수 있다.

BOJ 31056 Train Scheduling

DP[t][i][j]를 t 방향의 기차를 마지막으로 보냈고, A 기차를 i번까지, B 기차를 j번까지 보냈을 때 최소 비용이라고 하자.

단, 마지막으로 보낸 기차는 기다리지 않았어야 한다.

전이를 잘 시켜줘야 하는데, DP[t][i][j]에서 T 시간씩 기다려서 한 편씩 기차를 다 보내고 업데이트하는 작업을 반복하면 된다.

이 때 중복되는 연산이 많기 때문에 이를 모아서 계산하면 O(N^2)으로 해결할 수 있다.

구현이 정말 어려웠고, DP 식을 떠올리는 것도 정말 어려웠던 것 같다.

2/22(토) - 33일차

2차 선발고사를 봤다.