Educational Codeforces Round 143 (Rated for Div. 2)

A. Two Towers (0:02, +)

B를 뒤집어서 합친 후 끊는 것으로 생각할 수 있다. RR이나 BB가 최대 1번 등장하면 YES, 아니면 NO이다.

 

B. Ideal Point (0:06, +)

옆 두 점과 비교해 더 많기 위해서는 결국 [x, x] 형태가 존재하거나 [~,x], [x,~]가 하나씩 존재해야 한다. 이를 체크해주면 된다. A와 B 모두 \(O(N)\)에 풀 수 있으나 발상이 어려워서인지 제한이 작았다.

 

C. Tea Testing (0:13, +)

B에 대한 누적합 배열을 만들고, 각 차에 대해 이분탐색을 해주면 각 차를 온전히 먹는 사람과 일부만 먹는 사람을 구할 수 있다. 온전히 먹는 사람은 구간으로 나타나는데, imos법을 이용해 마지막에 처리해준 후 답을 구하면 깔끔하게 구현할 수 있다.

 

D. Triangle Coloring (0:33, +)

우선, RRR이나 BBB보다는 무조건 RRB와 RBB를 쓰는 것이 이득이다. \(\frac{n}{6}=k\)라 하면 \(2k\)개의 삼각형 중 RRB \(k\)개를 고르는 경우의 수 \({2k}\choose{k}\)개에 삼각형의 세 가중치가 모두 같은 경우 3방향으로 돌려줄 수 있으므로 하나당 3, 세 가중치가 \(a=b<c\) 형태인 경우 2방향으로 돌려줄 수 있으니 하나당 2를 곱해주면 된다.

 

E. Explosions? (1:11, +1)

폭발은 항상 마지막에 쓰는것이 이득이고, 폭탄을 던지는 몬스터한테는 기본 스킬을 쓰지 않는 것이 이득이다. 따라서 각 몬스터에게 스킬을 썼을 때 깎을 수 있는 최대 체력 합을 구한다면 그 중 최댓값을 전체 합에서 뺀 것이 답이 된다.

폭발의 구조 상 왼쪽과 오른쪽을 따로 구하는 것이 편하다.

\(dpl_i = i\)번째 몬스터에게 스킬을 썼을 때 왼쪽으로 진행되는 폭발의 최대 체력 합으로 정의하자.

우선 \(a_{i-1} < a_{i}\)라면 \(dpl_i = dpl_{i-1}+A_i\)이다. 아니라면, \(A_{i-1}\)을 \(A_i-1\)까지 깎아 놔야 한다. 그렇게 \(A_i-1, A_i-2, \)와 같은 방법으로 깎아나가다 \(A_j < A_i - (i-j)\)인 j를 만나면 \(dpl_j\)를 참조할 수 있다. 즉, 우리는 각 \(i\)에 대해 \(j<i\)이면서 \(A_j - j < A_i - i\)인 가장 큰 \(j\)를 알고 있어야 한다. 이는 스택 등을 통해 미리 구해둘 수 있고, 이를 구했다면 위와 같은 방법으로 DP를 각 \(i\)에 대해 \(O(1)\)에 구해줄 수 있다. 이를 양방향으로 구하면 폭발로 깎을 수 있는 최대 체력 합을 구할 수 있다.