_

1. Day1

1.1. Cloud Computing

컴퓨터와 작업을 F순으로 정렬해 놓고 매칭을 시키면 어떤 컴퓨터로 어떤 작업을 할 때 둘 중 하나의 C가 0이 될 때까지 양쪽 C가 감소한다. 따라서, i번째 컴퓨터까지 고려했을 때, j 번째 작업까지 고려하고 컴퓨터의 C는 k, 작업의 C는 0인 경우를 DP1[j][k], 컴퓨터의 C는 0, 작업의 C는 k인 경우를 DP2[j][k]라고 하고 DP로 문제를 풀 수 있다.

1.2. Global Warming

문제

모든 \(i\)에 대해 \(i\)번째 부터 끝까지 \(x\)만큼 증가시킬 때 LIS를 구하면 그 중 최댓값이 답이 된다.

\(i\)번째 위치부터 \(x\)만큼 증가시켰을 때 \(i\)를 사용하는 LIS의 길이는 (\(i\)부터 \(N\)까지 LIS의 길이) + (\(i+x\)보다 작은 값들로 이루어진 \(1\)부터 \(i-1\)까지 LIS 길이) 로 구할 수 있다. 둘 다 Segment Tree로 LIS를 구하는 방법을 사용하여 구할 수 있다.

1.3. Lottery

문제

\(O(N^2)\) 만에 모든 interval 쌍의 distance를 DP로 구해줄 수 있다. 쿼리는 \(k_j\)가 작은 순서대로 처리하면서 앞에서 구한 interval과 distance 에 대한 정보들을 Update하는 식으로 해결할 수 있다.

2. Day2

2.1. Fibonacci Representations

문제

2.2. Toys

문제

\(N = d_1 * d_2 * ... * d_k\)일 때 \((d_1-1) + (d_2-1) + ... + (d_k-1)\)로 가능한 값을 모두 구하는 문제다.

기본적인 아이디어는 Brute Force + 가지치기다. 먼저 관찰할 점은 위의 식에서 \(k\)는 최대 29라는 점이다. \(N\)의 모든 약수를 \(d\)라는 Vector에 넣고, \(d[i]\)를 증가하는 순서로 보면서 \(d[i]\)가 \(N\)을 나눌 때 답으로 저장하는 값에 \(d[i]-1\)을 더하고 \(N\)을 \(d[i]\)로 나누는 작업을 계속 해주는 Brute Force를 진행한다.

이때, 만약 현재 \(N\)을 \(x\)번 나눴는데, \(N\)이 \(d[i]^{29-x}\)보다 작다면, \(d[i]\) 이상의 약수에 대해 나눠볼 필요가 없으므로 break해줄 수 있다. (이 가지치기 작업을 안해주는 경우 59점인 듯 하다..)

2.3. Triangles

문제

쿼리를 통해 세 점이 CCW 인지 알려준다고 할 때 Convex Hull을 찾는 문제다.

두 점을 지나는 직선을 기준으로 모든 점들이 같은 영역에 존재하면 쉽게 CCW만 사용하여 Convex Hull을 구할 수 있다. 그러기 위해 가장 바깥 두 점을 찾아야 하는데 이 바깥 두 점을 찾기가 어렵다. 살짝 생각을 바꿔보면, 임의의 두 점을 지나는 직선을 기준으로 각 영역에 있는 점들로 Convex Hull 2개를 만들 수 있다. 그 후 두 Convex Hull을 합쳐주면 전체 Convex Hull을 구할 수 있다.