PS 일지 (1/3 ~ 1/23)

 

BOJ 17728 (Walls)

각 방벽에 대해 계산하는 쿼리 문제라고 생각하자. 방벽의 이동 경로는 왼쪽 -> 오른쪽 -> 왼쪽 -> 오른쪽 -> ... 과 같은 형태로 나타난다. 시작점이 INF 또는 -INF일 때 경로에서 꺾이는 점을 관리하면 문제를 해결할 수 있다. 방벽의 길이가 증가하면서 꺾이는 지점의 삭제가 일어나고, 이는 연결리스트와 같은 형태로 관리해줄 수 있다. pq를 사용하면 삭제되는 원소를 빠르게 구할 수 있고, 세그를 이용해서 답을 계산할 수 있다.

 

BOJ 17667 (Virus Experiment)

풀이가 다양하다.

 

풀이 1: https://qwerasdfzxcl.tistory.com/24 (타잔 알고리즘과 비슷하다.)

 

풀이 2: 풀이 1과 비슷한데, scc를 유파로 전부 들고 있으면서 dfs를 돌린다. 백엣지를 볼 때 그 점까지 전부 유파로 합쳐주고, 유파로 합치는 과정에서 새로 생기는 간선을 스몰투라지처럼 넣어주면 모든 scc를 구할 수 있다. (https://www.acmicpc.net/source/share/e758163c4e52442c97d68fae7448fb4d 이런 느낌으로 구현하면 될 것 같다.)

 

풀이 3: https://codeforces.com/blog/entry/68269?#comment-527158

보르부카 알고리즘과 비슷한 풀이다. 다음과 같은 방식으로 작동한다.

1. 초기에 원소가 점 하나인 집합 V개를 생성하고, 각 집합의 대표 정점을 유일한 원소로 둔다. 대표 정점이란 집합의 모든 원소에서 접근이 가능한 정점을 뜻한다.

2. 모든 집합을 한 번씩 순회하면서 각 집합의 대표정점에서 그래프 탐색을 한다.

2-1. 새로운 집합을 만나지 않고 종료하면 그 집합을 dead로 설정한다. (dead 상태인 집합은 순회하지 않는다.)

2-2. 새로운 집합을 만나게 되면 두 집합을 합쳐주고, 대표 정점을 새로운 집합의 대표 정점으로 놓는다. dead인 집합과 합쳐지면 dead 상태가 유지된다.

3. 모든 집합이 dead가 될 때까지 2번 과정을 반복해주고 각 집합의 대표 정점에서 그래프 탐색을 돌리면 답을 구할 수 있다.

 

BOJ 17666 (Remittance)

$$\sum_{k=0}^{N-1} A[i+k] \times 2^k$$

위 식의 값은 i-1 -> i 송금이 일어날 때만 감소한다는 것을 알 수 있다. (모든 인덱스는 mod N에서 생각) 이를 이용하면 각 i에 대해 i가 송금하는 양을 계산해둘 수 있고, 이 값이 모두 음이 아닌 정수라면 항상 가능함을 증명할 수 있다. (초기 상태가 전부 0인 경우, 최종 상태가 전부 0인 경우는 예외다.) 이 값들은 이분탐색 / bigint + 점화식 등으로 계산할 수 있다.

 

BOJ 25422 (Seesaw)

(무게중심, 원소 개수)를 2차원 평면에 찍어보면 삼각형 형태로 점들이 찍힌다. x좌표 이동범위를 최대한 제한해야하기 때문에 전체 무게중심에 가까운 점들만 써야한다. 사용하는 점의 모든 x좌표가 전체 무게중심 이하인 상태에서 시작해서 작은 것부터 1개씩 바꿔주는 시행을 N-1번 반복해주면 모든 x좌표가 전체 무게중심 이상이 될 것이고, 이 과정에서 나온 집합 중 해가 반드시 존재한다. 이 과정에서 나온 모든 집합이 valid함을 증명할 수 있다.

 

BOJ 17665 (Triple Jump)

가능한 (a, b) 쌍은 O(N)개이다.

 

BOJ 10847 (자카르타의 마천루)

(위치, 점프거리)를 정점으로 놓으면 방문하는 정점 개수가 1.5승 스케일임을 증명할 수 있다. 이 그래프에서 bfs를 돌리면 문제를 해결할 수 있다. 방문 여부를 비트셋으로 관리하면 구현이 편하다.

 

BOJ 15844 (Land of the Rainbow Gold)

v-e+f를 이용해서 컴포넌트 개수를 세줄 수 있다. v, e, f는 2차원 쿼리 꼴이라 PST로 간단하게 계산할 수 있다. f에서 예외가 한 가지 있다는 점을 유의해야한다.

 

BOJ 17635 / 16793 (다리 / Collapse)

간선 업데이트를 루트개씩 묶어서 처리해주면 된다. Collapse의 경우 쿼리로 들어온 지점 왼쪽과 오른쪽 컴포넌트를 각각 세줘서 더해주면 풀 수 있다. (+ Collapse는 offline dynamic MST를 이용해서 로그제곱에도 풀 수 있다. 이는 APIO Toll과 비슷한 방식으로 풀 수 있다.)

 

BOJ 25017 (플래피 버드)

세로선 기준으로 스위핑을 하자. 세로선과 겹치는 구간의 합을 계산할 때, 안 겹치는 구간의 합을 빼주는 방식의 접근을 하면 문제가 간단해진다. 두 수열 A, B가 있을 때, 원소 업데이트와  A[i] + B[j]의 최댓값 쿼리(단, i<j)를 처리하는 형태의 문제로 바뀌게 되고 이는 세그먼트 트리로 구현할 수 있다.

 

BOJ 25020 (코딩 테스트)

홀의 결혼정리를 이용하면 $\min_{l \le i \le j \le r}f(i, j)$ 형태로 답을 표현할 수 있다. 이를 제곱 DP로 계산해주면 섭태 3, cht를 이용해서 계산해주면 섭태 4를 풀 수 있다. 100점을 받기 위해서는 dnc를 해야한다. 현재 dnc(s, e)가 호출된 상태라고 하자. mid = (s+e)/2라고 하면, s <= l <= mid && mid+1 <= r <= e인 (l, r) 쿼리들을 이 dnc 함수에서 전부 처리할 것이다. 섭태 4 풀이를 이용해서 왼쪽 절반과 오른쪽 절반을 각각 처리해주고 나면 $\min_{l \le i \le mid < j \le r}f(i, j)$만 구하면 된다. 이는 두 개의 컨벡스헐의 공통접선을 구하는 형태로 해석할 수 있고, 공통접선의 기울기를 pbs와 cht로 계산할 수 있다. 여담으로 나는 persistent lower hull(...)을 짜서 풀었다. 모노톤 체인 알고리즘에서는 스택만 사용하기 때문에 트리 형태로 원소를 저장하면 pst를 안 쓰고 스파스테이블만 써서 lower hull을 persistent하게 관리할 수 있다.

dnc를 안 하고 처음부터 pbs를 써서 풀 수도 있을 것 같은데 안 짜봐서 잘 모르겠다.

 

BOJ 27173 (수열과 쿼리 43)

루트가 보인다고 수열과 쿼리 28처럼 풀 생각은 하지 말자. 3번 연산이 퍼텐셜을 박살낸다. 루트 업데이트를 $\log \log x$번 해주면 1이 되기 때문에 이를 이용하면 $O(\log \log MAX) 데이터로 레이지 정보를 관리할 수 있다.

 

BOJ 17636 (가로등)

2차원 평면에 점이 N개 있을 때, 점 업데이트 / 2차원 구간합 쿼리를 오프라인으로 2d세그 없이 처리하는 방법을 먼저 알아보자.

모든 쿼리가 업데이트 이후에 주어진다면, 문제를 세그 + 스위핑으로 해결할 수 있다. 이를 이용하여 dnc를 한다. dnc(s, e)가 호출된 상황을 생각하자. mid = (s+e)/2라고 하고, 업데이트 시점이 [s, mid]인 업데이트와 쿼리 시점이 [mid+1, e]인 쿼리만 고려하자. 이를 세그 + 스위핑으로 계산해서 답을 갱신해주면 모든 dnc가 호출된 이후에 모든 답이 계산되어있을 것이다. 이 방식을 이용하면 17636도 풀 수 있다.

 

BOJ 15977 (조화로운 행렬)

정렬을 하면 lis 형태의 문제로 바꿀 수 있다. 여기서 dnc를 이용하면 2d세그 없이 풀 수 있다. dnc(s, e)를 "호출된 시점에서는 ans[1]~ans[s-1]이 모두 계산되어 있으면서, ans[1]~ans[s-1]에 대한 ans[s]~ans[e]가 전부 계산되어있고, 리턴되는 순간에는 ans[s] ~ ans[e]가 모두 정확하게 계산되어있는 함수"라고 하자. dnc(s, mid)를 호출하고, ans[s]~ans[mid]의 값을 이용해서 ans[mid+1]~ans[e]의 값을 갱신해주고, dnc(mid+1, e)를 호출하면 dnc함수를 구현할 수 있다. 따라서, dnc(1, n)을 호출하면 문제가 풀린다.

 

BOJ 22028 (렉)

각각의 이동에 의해 더해지는 값을 적당한 평행사변형에 ax+by+c를 더해주는 연산으로 표현할 수 있다. 이는 세그 + 스위핑으로 해결할 수 있다.

대각선 방향 이동을 어떻게 쪼갤지 생각하는게 제일 어려운데, 아래 그림처럼 쪼개면 편하다.

 

BOJ 22027 (통신망)

dfs tree를 잡고 생각하자. 지운 간선이 단절선 / back edge / 나머지 인 경우를 각각 풀면 된다.

단절선인 경우와 back edge인 경우는 꽤 간단하게 풀 수 있고, 나머지 경우는 그 간선 기준으로 dfs tree의 윗부분과 아랫부분을 각각 계산해주면 풀 수 있다. 디테일은 직접 생각해보자.

 

BOJ 25014 (열차의 이동)

두 경로를 잇는 최단경로를 생각해보면 그 최단경로의 끝점까지 열차를 빼내야한다는걸 알 수 있다. 그 과정을 그림으로 나타내면 대충 이런 형태로 나타난다.

1 -> 2 -> 3 -> 4 순서로 열차가 이동하는데, 이 과정을 그대로 시뮬레이션하는 것은 꽤 복잡하다. 4 -> 3 -> 2 -> 1 순으로 생각하면 그리디하게 열차를 움직여도 된다는 것을 알 수 있고, 이 과정을 투포인터로 구현할 수 있다.

 

BOJ 18186 (라면 사기)

예전에 풀었지만 기억이 안 나서 다시 풀어봤다. 현재 i-1번째까지 전부 산 상태라고 할 때, A[i], A[i+1], A[i+2]의 대소관계에 따라 해야하는 전략이 정해져있음을 증명할 수 있다. A[i] < A[i+1] && A[i+1] >= A[i+2] 케이스가 제일 어려운 경우인데, A[i]와 A[i+1]에서 min(A[i], A[i+1]-A[i+2])를 빼준 후, A[i]와 A[i+1]과 A[i+2]에서 A[i]를 빼주는 것이 최적임을 증명할 수 있다. 그리디가 된다는 믿음이 없으면 이 케이스에서 포기하고 다른 방법으로 시도했을 것 같다.