Codeforces Round #844 (Div.1 + Div.2)

https://codeforces.com/contest/1782

미래에 VK 라운드가 하나 더 있어서 풀었다.

사실 tourist 셋이 정신건강에 좋지 않다고 생각하는데 또 엄청 나쁘냐고 하면 애매해서 까기도 애매하고

1차적인 답만 구하는게 아니라 굳이 그 답이 나오는 상황을 구현해야하는게 좀 많이 불편했다.

G는 딱히 문제를 읽지도 않았지만 tourist의 답을 보면 3중 if + 4중 for을 박고 앉아 있으니 참...

 

A. Parallel Projection

 

단순 구현이다. 

네 면 중 어디를 들려서 도착할지 결정해주면 된다.

 

B. Going to the cinema

 

1번부터 i번째 사람이 간다고 가정하고 이것이 가능한지 판단해주면 된다.

 

C. Equal Frequencies

 

i 종류의 char를 사용한다고 가정하자.

그렇다면 단어 내에 제일 많이 포진된 i개의 char을 고르는 것이 제일 현명하다.

-> 여기까지 해주면 몇 개의 포지션을 바꾸는게 최선인지 쉽게 구할 수 있음

 

이제 문제에서는 balanced string 자체도 요구한다.

어떤 문제에서 주어진 s의 char x를 마주하였을 때 이 x가 변해야하면 변할 수 있는 애로 바꾸고 그렇지 않으면 냅둔다.

 

D. Many Perfect Squares

 

square이 되는 애들만 고르면 ai + x, ... , aj + x 느낌으로 일부만 뽑힐 것이다.

제일 앞에 있는 i값을 1번부터 n번까지 iteration 시키자.

m[y] = (x = y^2 - ai 일 때 가능한 최대 square의 개수)라고 하자.

ai + x = p^2, aj + x = q^2이라고 할 때 aj - ai = (p + q)(p - q)가 된다.

따라서 ai, aj 쌍에 대해서 sqrt의 시간으로 모든 p, q 쌍을 구하고 m[p]++를 해줄 수 있다.

그러면 총 필요한 시간은 n^2 sqrt(MAXA) 가 되고 이는 충분하다.

 

E. Rectangle shrinking

 

이것도 답을 1차적으로 구하기는 쉬운데 구현에 조금 시간이 걸렸다

그냥 당연하게 일단 모든 사각형을 L을 기준으로 정렬한다.

그다음에 각각 위와 아래에 대해서 마지막으로 도달한 칸을 up, down이라고 한다.

그러면 다음 사각형을 마주하였을 때 up < R이라면 ans += R - max(up, L)을 해주는 식으로 더해주면 된다.

이는 현재 사각형이 나머지 사각형 중에서 제일 좌측에, 기존의 사각형 중에 제일 우측이므로 가능하다.

 

이제 정확하게 그 사각형들을 배치해주어야 한다.

이파트는 앞에서부터 했던 답구하기와 달리 반대로 해준다.

이제 만약에 뒤에 있는 사각형이 내가 차지하고 있는 적당한 공간 [L, R]을 침범한다면 이를 [L, up]로 바꿔주면 된다.

 

F. Bracket Insertion

 

우선적으로 생각해볼 수 있는 것은 항상 그렇듯 bracket sequence를 숫자열로 바꾸는 것이다.

( = +1, ) = -1, 시작은 0이라고 생각하자.

그렇다면  () = {0, 1, 0},  (()) = {0, 1, 2, 1, 0} 으로 표현할 수 있다.

이때 ()를 x라는 숫자 뒤에 추가한다면 {... x, x + 1, x ... }이 되고, )(를 추가하면 {... x, x-1, x ...}이 된다.

이때보면 알 수 있다시피 x 뒤에 ()나 )(를 추가한다고 기존에 있던 x가 바뀌거나 사라지지 않는다.

따라서 마지막에 regular bracket sequence가 되려면 처음부터 끝까지 regular하여야 한다.

 

x 뒤에 ()이 온다면 x, x+1, x가 생성된다.

x 뒤에 )(이 온다면 x, x-1, x가 생성된다.

만일 x가 아닌 아무 숫자 뒤에 ()이 온다면 x가 그대로 생성된다.

만일 x가 아닌, 1 이상의 숫자 뒤에 )(이 온다면 x가 생성된다.

-> 따라서 x의 개수를 의미하는 대충의 dp를 할 수 있음을 예상할 수 있다.

-> 하지만 9가 있는 숫자열에서 0의 개수의 기댓값과 1이 있는 숫자열에서 0의 개수의 기댓값이 다르니 단순하게는 불가

 

f(n, x) : [x]로 시작했을 때 n번의 추가 이후에 sequence가 살아남을 확률

그렇다면 당연히 f(0, x)은 0번 추가했고 [x]만 있는 것이니 1이다. (초항)

처음에 ()가 가해지면 [x, x+1, x]가 되고 n - 1번 남으며, )(가 가해지면 [x, x-1, x]가 되고 n - 1번이 남는다.

-> 각각에 나머지 n - 1번 중에서 a번, b번, c번 가해졌다고 하자.

f(n, x) = sum f(a, x)f(b, x + 1)f(c, x)*p*C(a, b, c) + sum f(a, x)f(b, x - 1)f(c, x)*q*C(a, b, c)

-> 위의 식을 잘보면 b빼곤 두 항이 일치한다.

f(n, x) = sum (pf(b, x+1) + qf(b, x-1)) * sum f(a, x)f(c, x)C(a, b, c)

-> 뒤에 부분을 따로 g(n - 1 - b, x)라고 부르면

f(n, x) = sum (pf(b, x+1) + qf(b, x-1)) * g(n - 1 - b, x) 이다.

이때 f하나 g하나를 각각 계산할 때에는 O(n)의 시간이 걸리며, 총 필요한 개수가 각각 n^2이다.

따라서 총 시간복잡도는 O(n^3)이고 시간내에 답인 f(n, 0)을 구할 수 있다.