Educational Codeforces Round #127 (Div.2)

https://codeforces.com/contest/1671

Dashboard - Educational Codeforces Round 127 (Rated for Div. 2) - Codeforces

E솔이 무려 500명정도가 나왔던 쉬운 라운드. 하지만 나에겐 아직도 어렵다

 

A (00:02)

2글자 이상의 연속된 문자는 무조건 만들수 있다. 단순 구현문제

 

B (00:07)

x - 1, x, x + 1은 뭔가 좀 불편하니까 x - 2, x - 1, x로 보면, 바로 전 수에 맞춰서 값을 빼기만 하면 된다는 사실을 금방 알 수 있다. 이것도 단순 구현문제

 

C (00:25)

가격이 싼 것부터 사는게 당연히 이득이므로, 정렬 후 누적합 배열을 만든다. 그리고 각 물품마다, 어느 날짜까지 살 수 있는지 구한다.

날짜를 k라고 하면, ￦(p_i + ki <= x￦)인 최대 k를 찾으면 된다. (첫째날부터 가격이 오르는건 아니므로, 정확히는 k+1이 해당하는 날짜이다)

 

D (00:49)

배열 A의 최댓값과 최솟값을 max, min이라 하자. min과 max 사이(포함)에 해당하는 값들은 그냥 무시할수 있다. 답에 영향을 주지 않기 때문이다. 이제 범위 밖의 수를 어떻게 처리할지 생각해보면, 맨 끝으로 가는 경우와 중간에 끼는 경우를 나누어 계산하면 된다는 것을 알 수 있다. max와 min이 둘다 같은쪽 끝에 오는 경우가 있다 생각할수도 있지만.. 조금만 생각해보면 깨달음을 얻을 것이다. 화이팅

 

E (--:--)

서브트리에서의 서로다른 문자열의 수를 L, R이라고 하자.

두 서브트리가 같은 경우: L^2 (=L*R)

-> 두 서브트리가 같다면 어자피 L=R이다

두 서브트리가 다른 경우: L*R*2

-> L, R을 바꾸는 경우가 있으므로 2를 곱해준다.

가 되고, 이는 문자열을 정렬하는 방법으로 확인할 수 있다. 문자열 비교를 생각해보면 O(X^2)가 나올것 같지만, 완전이진트리이기 때문에 시간복잡도는 O(XlgX)이므로, 짧은 시간에 동작한다. (X=2^N)

 

 

49분 4솔이 어떻게 600위밖에 안됨 ㅠ