Educational Codeforces Round 150 (Rated for Div. 2)

풀이는 대개 다 쉬운 편. 디버깅 매드무비를 찍어야 한다.

 

A. Game with Board

 

처음에 N > 4라고 가정하자.

그러면 Alice가 1을 2개 남기고 모두 합쳐버리면, Bob은 1 2개를 무조건 합쳐야 하고 Alice가 승리한다.

만일 N <= 4라면 Alice가 뭔 짓을 하던지 진다.

 

B. Keep it beautiful

 

그냥 그대로 구현해주면 된다.

앞쪽 부분과 뒤쪽 부분의 벡터를 나눠서 a, b로 관리하자.

만약에 b.empty()이라면

1) a.back()보다 큰 수가 들어왔을 때 그대로 a 뒤에 넣어주면 되고

2) a[0]보다 작은 수가 들어왔으면 b에 최초로 넣어주면 된다.

만약에 !b.empty()라면 b.back()보다 크고 a[0]보다 작은 수가 들어왔다면 b 뒤에 넣어주면 된다.

그 외의 경우에는 원소가 들어갈 수 없다.

 

C. Ranom Numbers

 

각 문자가 있는 제일 오른쪽 위치와, 각 문자의 개수에 대한 prefix sum을 안다면 O(1)에 value를 구할 수 있다.

따라서 목표는 그냥 모든 s의 단어를 A, B, C, D, E로 한 번씩 바꿔봐서 O(slen * 5)로 모든 value를 구해보는 것이다.

 

현재 바뀌는 단어가 제일 오른쪽 단어라면, 제일 오른쪽 위치가 바뀔 수 있으니, 두 번째로 오른쪽 위치도 필요하다.

prefix sum은 바꾸면서 갱신해주는게 아니라, i번째 단어가 바뀌었으면 i번째 단어가 더해지는지 빼지는지를 관리한다.

즉 제일 오른쪽 단어들의 위치 ff[x]와 prefix_sum[y]에 대한 점수를 구하고, 

(기존 a[i]값에 의한 value의 변화)를 빼주고 (새로운 a[i]값에 의한 value의 변화)를 더해주면 된다.

 

D. Pairs of Segments

 

이 문제는 Minimum to remove이므로 Maximum to not remove를 구해도 된다. (Pair을 최대한 많이 뽑는 방법)

어떤 segment pair {[L1, R1], [L2, R2]}가 있다고 하자. (R1 <= R2)

이때 현재 n개의 segment에 대해서 R2값이 최소인 pair {[L1, R1], [L2, R2]}를 고르는 것은 손해가 아니다.

 

claim) R2가 최소인 pair을 고른다면 무조건 pair을 최대한으로 뽑을 수 있다.

pf) R2가 최소인 경우에 pair을 최대로 뽑을 수 없다고 가정하자. 그러면 최대로 pair을 뽑을 수 있는 방법들을 생각해보자.

-> 이때 제일 왼쪽에 있는 segment의 두 번째 R값이 제일 최소인 뽑기 방법이 있을 것이다.

-> 그렇다면 그 pair는 {[L1', R1'], [L2', R2']}이라고 하자.

-> R2 < R2'이라면 위의 pair을 {[L1, R1], [L2, R2]}로 바꾸어도 조건을 만족하여 최대이고, 그러면 귀류가정에 모순

-> 따라서 R2 = R2'이고 항상 segment의 집합에 대해서 R2가 최소인 pair을 고르는 것은 최대로 뽑는 방법이다.

 

그래서 그냥 R에 대해 정렬해주고 O(N)으로 매번 [L[i], R[i]]에 대해 겹치는 [L[j], R[j]] (j < i)가 있는지 확인하면 된다.

 

E. Fill the Matrix

 

흰색 칸들을보자.

어떤 행에 대해서 [L, R]이 모두 흰색이라고 가정하자.

그러면 R - L + 1개의 숫자를 소비하여 R - L만큼의 Beauty를 얻을 수 있다.

따라서 당연히 R - L이 큰 적당한 구간을 선택하는 것이 제일 효율적이다. 

 

맨처음에는 구간 [0, N - 1]을 보자.

제일 처음으로 검은 칸이 나오는 열을 x라고 하고, y번 행부터 검은색이라고 가정하자.

그렇다면 0번 행 ~ y - 1번 행은 구간 [0, N - 1]을 그대로 사용할 수 있고,

y번 행부터는 구간을 쪼개서 [0, x - 1]과 [x + 1, N - 1]로 사용하여야 한다.

 

그러면 이제 매번 제일 긴 구간을 선택해야 하므로

{ 구간의 길이, L, R, 처음으로 L - 1번 열이나 R + 1번 열에서 검은 칸이 나오는 행 }이라는 값을 Priority_queue에 넣자.

-> { len, L, R, black } 이라고 부르고, 위에서 정의한 것처럼 x, y를 정의하자.

-> 그러면 (y - black)번 [L, R]의 구간을 사용할 수 있다.

-> 따라서 beauty += (R - L) * (y - black), m -= (R - L + 1) * (y - black)을 해주면 된다.

-> 만일 m <= (R - L + 1) * (y - black)이라면, [L, R]을 최대한으로 쓰고, 남은 것들이라도 일렬로 넣어주면 된다.

-> 이후 Priority queue에는 {x - L, L, x - 1, y}와 {R - x, x + 1, R, y}를 넣어주면 된다.

 

F. Monocarp and a Strategic Game

 

아직 AC를 못 받아서 확실하지는 않다.

 

마지막에 human, orc, elf, dwarf의 숫자를 A, B, C, D라고 한다면 Score = (A - B)^2 + (C - D)^2이다.

따라서 각각의 a, b, c, d에 대해서 {a - b, c - d}인 벡터라고 생각한다면

N개의 벡터중에서 적당한 subset을 골라서 V * V의 최댓값을 구하면 되는 것이다.

 

답이 되는 벡터를 V라고 하자.

만일 subset에 포함된 벡터 중에서 V * v < 0인 v가 있다면, v는 없는게 이득일 것이다.

즉, subset에 포함된 벡터들은 모두 어떤 V에 대해서 V * v  > 0을 만족할 것이다.

그러면 이제 투 포인터를 잘 굴리면 된다.

어떤 V에 대해서 시계로 90도, 반시계로 90도 위치에 있는 index를 찾고 잘 계산해주면 된다.

 

이걸 잘하면 AC를 받을 것이라고 예상된다. (62번 테케까지는 갔다.)