_

1. 1차 대회

2. 2차 대회

2.1. 초등부

2.1.1. 사각형 면적

문제

문제에서 주어진 조건 그대로 구현하면 된다.

현재 종이의 세로, 가로 길이 A, B를 갖고 있고, 새로운 점 (X, Y)가 입력으로 주어졌다고 하자.

• \(A \leq X \) 또는 \(B \leq Y \)이면 이 입력은 무시하고 넘어간다.

• 그렇지 않은 경우

  • \(A\times Y \leq B\times X \) 인 경우 \(A = X \)
  • \(A\times Y > B\times X \) 인 경우 \(B = Y \)

2.1.2. 계산 로봇

문제

2차원 DP 테이블을 통해 해결할 수 있다.

\(DP[i][j]\)를 (i, j)위치의 저장 값이라 정의하자.

이때, \(DP[i][j]\)로 가능한 값은 \(DP[i-1][j-1] + D_{i-1, j-1} \), \( DP[i][j-1] + D_{i, j-1} \), \( DP[i+1][j-1] + D_{i+1, j-1} \) 중 최댓값임을 관찰할 수 있다. (그보다 먼 값들은 이미 세 DP 값 중 최소 하나의 값에 고려되어 있다.)

따라서 DP 테이블을 \(O(N^2) \)에 채울 수 있으며, 답은 DP 테이블 내 최대값이 된다.

2.1.3. 괄호의 값 비교

문제

괄호 문자열의 길이가 최대 3,000,000 이므로 long long이나 int로 단순히 계산하기에 괄호의 값은 매우 크다.

아직 닫히지 않은 여는 괄호가 k개 있고, ()가 등장하면, 괄호의 값에 \(2^{k+1}\)이 더해지며, 이러한 () 괄호들의 값을 각각 구하여 더해주면 전체 괄호 문자열의 값을 구할 수 있다.

따라서 괄호의 값은 여러 \(2^k \) 형태의 값들의 합으로 표현할 수 있다.

이 값들을 이진법 표현으로 배열에 저장하고, 마지막에 받아올림을 구현해주면 두 괄호의 값의 크기 비교를 두 이진법 수의 크기 비교를 통해 구현할 수 있다.

2.1.4. 그래프 균형 맞추기

문제

그래프를 DFS하여 DFS Spanning Tree를 구해주자. 또, 루트 노드에서부터 거리가 짝수인 노드는 검정색, 거리가 홀수인 노드는 흰색으로 coloring을 해주자.

주어진 그래프는 양방향 그래프이기 때문에 DFS Spanning Tree 에서 이 그래프의 에지는 tree edge와 back edge로 구분할 수 있다.

루트 노드에 임의의 가중치(ex. 0)을 부여하고, tree edge에 주어진 간선의 가중치가 그 간선이 잇는 두 정점의 가중치 합이 되도록 정점들의 가중치를 부여해준다. 이 경우 모든 노드의 가중치가 하나로 결정된다.

만약 루트 노드의 값을 x로 업데이트한다 가정하자. tree edge에 주어진 간선 가중치를 만족하기 위해서는 모든 검정색 노드의 가중치가 x만큼 증가하고, 모든 흰색 노드의 가중치는 x만큼 감소해야 한다.

이 성질을 이용하여 back edge들도 간선 가중치를 만족하도록 하는 x값을 구해줘야 한다. 이때 두 가지 경우가 생긴다.

• x값이 하나로 결정

이는 같은 색의 노드를 연결하는 back edge가 있는 경우 발생한다.

만약 두 검정 노드를 연결하는 간선의 가중치가 \( v_e \), 그 간선이 잇는 두 정점의 가중치 합이 \(v_n \)라 하면 \(x\)값은 \( {v_e-v_n}\over 2 \)로 결정된다.

두 흰색 노드를 연결하는 경우도 비슷한 방식으로 x값을 결정해줄 수 있다.

• 모든 값이 x값으로 가능

같은 색의 노드를 연결하는 back edge가 없는 경우 발생한다.

이 경우, x값은 아무런 제한이 없기 때문에 총 비용을 최소화하는 x값을 구해주어야 한다.

이때 x값은 검정 노드의 가중치에 -1을 곱한 \(-v_x \), 그리고 흰 노드의 가중치 \(v_y\) 값들 중 중간값인 경우 전체 가중치 합이 최소가 된다.

이렇게 x값을 구한 다음 마지막으로 전체 간선 가중치 조건이 맞는지 검사하여 이렇게 구한 x값이 유효한지 검사해주면 문제를 해결할 수 있다.

2.2. 중등부

2.2.1. 계산 로봇

초등부 1번 문제와 같다.

2.2.2. 누적 거리

문제

누적 합 등을 전처리를 통해 DP로 저장해 두어 각 쿼리를 \(O(\log{N}) \)에 처리할 수 있다.

위치(\(x_i\)) 순서로 마을 정보를 정렬하자.

1부터 i까지 거주 중인 사람 수의 합을 DP1[i]라 하자. ( \( DP1[i] = \sum_{k=1}^i a_k \) )

또, 1부터 i까지 거주 중인 사람 수에 위치를 곱한 값의 합을 DP2[i]라 하자. (\(DP2[i] = \sum_{k=1}^i {a_k \times x_k} \) )

후보 장소 q가 주어지면, q보다 작거나 같은 최대의 마을 위치를 \(x_i\)라 하자. 이는 Binary Search로 \(O(\log{N}) \)에 구할 수 있다.

이때 1부터 i번째 장소에 사는 사람들의 누적 거리 합은 \( a_1 \times (q-x_1) + a_2 \times (q-x_2) + ... + a_i \times (q-x_i) = DP1[i] \times q - DP2[i] \)임을 알 수 있다.

이와 비슷하게 q보다 큰 위치의 마을들에서 누적 거리 합도 비슷한 DP 배열 2개를 뒤에서부터 누적합을 계산하면 구할 수 있다.

이렇게 각 쿼리에 대해 q보다 작은 위치의 마을과 큰 위치의 마을의 누적 거리 합을 나누어 구하면 답을 계산할 수 있다.

2.2.3. 일이 이어져야 좋다

문제

금광 세그 에서 사용하는 아이디어를 사용하여 쿼리마다 \(O(\log{N}) \)에 처리해줄 수 있다.

N값이 주어지면 고려해야 하는 \(S_i\)의 개수는 \(O(\log{N}) \)개로 결정된다.

각 \(S_i\)에 대해 내부에 연속한 1의 최대 개수, 문자열 왼쪽에서 연속한 1의 개수, 문자열 오른쪽에서 연속한 1의 개수를 구해준다. 이는 \(S_{i\over 2}\)의 값들을 이용하여 각각 O(1)에 구해줄 수 있다.

각 쿼리를 처리할 때, 금광 세그의 아이디어와 같이 현재 구간에 대해 마찬가지로 내부에 연속한 1의 최대 개수, 문자열 왼쪽에서 연속한 1의 개수, 문자열 오른쪽에서 연속한 1의 개수를 유지하면, Segment Tree와 같이 \( \log{N} \)개의 구간에 대해서만 고려하여 연속한 1의 최대 개수를 구해줄 수 있다.

2.2.4. 공통 괄호 문자열 사전

문제

Suffix Array를 사용하여 해결할 수 있다.

2.3. 고등부

2.3.1. 헬기 착륙장

문제

임의의 A, B에 대해 최대 원의 개수는 \(\sqrt{2(A+B)} \)개, 대략 500개 이하가 된다. 이 최대 원의 개수를 K라 하자.

DP를 통해 원 i개, 빨강 페인트를 j개 사용할 때 만들 수 있는 서로 다른 헬기 착륙장의 개수를 DP[i][j]라 하자.

DP[i][j] = DP[i-1][j] + DP[i-1][j-i] 점화식으로 DP 테이블을 채울 수 있다.

이후 원 i개, 빨강 페인트를 j개 이하로 사용할 떄 만들 수 있는 서로 다른 헬기 착륙장의 개수를 DP2[i][j]라 하자. 이는 DP[i][j]를 이용하여 쉽게 구할 수 있다.

쿼리로 A, B가 주어지면, 1부터 K까지의 값 i에 대해 원이 i개 있을 때 빨강 페인트 A개 이하, 파랑 페인트 B개 이하를 사용하여 만들 수 있는 서로 다른 헬기 착륙장의 개수를 구해준다.

이 빨강 페인트를 \({{i\times(i+1)}\over 2} - B \)개 이상, \(A\)개 이하로 사용해야 하므로 다음 식을 통해 구할 수 있다. \(DP2[i][A] - DP2[i][{{i \times (i+1)} \over 2} - B - 1] \)

이를 이용하면 각 쿼리를 \(O(K) \)안에 처리하여 문제를 해결할 수 있다.

2.3.2. 그래프 균형 맞추기

초등부 4번 문제와 같다.

2.3.3. 가장 긴 공통 괄호 문자열

Suffix Array를 사용하여 중등부 4번 문제와 같이 해결할 수 있으며, Parametric Search와 Hashing을 사용해서도 해결할 수 있다.

Parametric Search + Hashing

S(A, B)에서 가장 길이가 긴 문자열 S의 길이가 k 이상이라고 하자.

A와 B 각각에서 다음 처리를 해준다.

• 각 위치 i에 대해 i에서 시작하면서 길이 k 이상인 가장 짧은 올바른 괄호열을 Hasing하여 저장해준다.

  • 이는 Stack을 이용하여 i에서 시작할때 i부터 j까지 문자열이 올바른 괄호 문자열이 되는 j값들을 Stack에 넣어 관리하면서 길이 k이상이 유지되면서 i부터 j가 최소 길이가 되도록 Stack의 원소를 제거하는 방식으로 처리할 수 있다.

이렇게 Hashing한 값들을 \(H_A, H_B \)에 저장했다고 하자.

• 만약 S(A, B)에서 가장 길이가 긴 문자열의 길이가 k 이상인 경우 \(H_A \)와 \(H_B \)는 반드시 하나 이상의 원소를 공유해야 한다. (S의 prefix 중 길이 k이상의 가장 짧은 올바른 괄호열이 \(H_A, H_B \)에 반드시 포함되어 있기 때문)

• 마찬가지로 만약 S(A, B)에서 가장 길이가 긴 문자열의 길이가 k보다 작다면 \(H_A \)와 \(H_B \)는 서로 공유하는 원소가 없어야 한다.

따라서 l값을 이분 탐색하면서 답이 k이상인지, 그렇지 않은지 \(O((|A|+|B|)) \)시간복잡도로 계산해주면 해결할 수 있다.

2.3.4. 맛집 추천