Codeforces Round #850

https://codeforces.com/contest/1785

 

하이고 내 점수

 

A. Monsters (easy version)

 

간단하다.

최대한 monster들을 연속하게 만들어주고 spell 2를 쓰면 된다.

(전체 체력) - (spell 2의 피해량) = (spell 1의 횟수)이기에 spell 2의 피해량을 최대로 늘려주면 되기 때문이다.

따라서 대충 정렬해주고 1, ... 1, 2.., 2, 3...,3, 4... 로 만드는데 필요한 비용을 더해주면 된다. (O(nlgn))

 

B. Letter Exchange

 

그냥 구현이다.

교환은 i) 서로 필요한 것을 주는 2인 교환 ii) 3명이 서로 필요없는 것을 주고 필요한 것을 받는 교환 이 있다.

어떠한 방법을 사용하더라도 ii)에서 발생하는 비효율을 줄일 수 없다.

그렇기에 1) 일단 i가 가능한 경우 i를 시도 2) i가 불가능하면 ii를 진행  하는 방법을 구현하면 된다.

 

C. Monsters (Hard version)

 

진짜 많은 방법을 생각했었다.

1) 앞에서부터 하는데 i번째 원소가 뒤에 추가 되었을 때 lgn으로 하는 것이 가능한가?

2) 제일 작은 원소에서부터 (중간에서부터) 어떠한 방식으로 잘 계산하면 가능한가?

-> 이 세 가지를 베이스로 갖은 생각을 했었다.

대회 중에서는 1)로 떠오르는게 전혀 없고 애초에 그런게 의도면 easy를 안 냈을 거라 판단해 2)에 집중했었다.

prefix sum처럼 응용되는 방식, 구역마다 다르게 숫자가 적용되는 방식 등을 생각하는데 뭐가 안 떠올랐다.

아주 잠시 a[i] <= n이라는 제한으로 무언가가 되나 고민했는데 이것은 2와 별 다를게 없다.

 

그래서 1시간 넘게 버리고 받아들인게 1)인데...

원래 있던 {1, 1..., 1, 2..., 2, 3, ..., 3, 4...}의 계단이 i번째 원소가 끼어들면 어떻게 변화하는지 관찰했다.

애초에 정렬된 형태다 보니 set이 생각나고 어떻게 이게 변화하는지 관찰하는 방향으로 갔었다.

대충 구현을 했는데 문제가 되는 상황이

-> {3, 3, 3}이 {1, 2, 3}이 되어있는데 여기에 2가 끼면 1이 되야하는데 (2가 이미 있음) + (1은 본인 숫자도 아님) -> :(

 

그러니 당연히 생각하지 못한 3안이 답이었는데 3) 뒤에서부터한다 였다. 

{3, 3, 3, 2}가 {2, 3, 3, 1}이 되어있는데 여기서 2가 빠지는 상황을 고려하는 것은 위에서보다 훨씬 간단하다.

우선 계단을 만드는데 쓰이지 않은 숫자들을 모두 left에 넣어뒀다고 하자.

어떤 숫자가 빠진다면

i) 그냥 원래 아무것도 안하던 숫자라서 아무일도 일어나지 않는다 -> 당연히 아무런 작업도 해줄 필요가 없음

ii) 원래 무언가 하던 숫자인데 뒤에 있는 숫자들이 채워줘서 층수에는 변화가 없다.

    -> 그러면 left.lower_bound(a[i])가 채워서 들어가 주는 것이므로 변화는 (들어오는 숫자) - a[i]

iii) 원래 무언가 하던 숫자인데 숫자가 남는게 없어서 층수마저 한 층 줄어든다.

    -> 기존에 있던 계단에서 a[i]가 마지막 층을 담당하고 있었다고 생각해도 무방하다. (심지어 층수 > a[i] 더라도)

    -> a[i]가 층수를 담당하던 것만 제외시켜버리면 되므로 그렇다면 변화는 (층수) - a[i]

https://codeforces.com/contest/1785/submission/193016587

 

https://codeforces.com/contest/1785/submission/192316174

Jiangly의 버전인데 진짜로 뭐한건지 모르겠음

 

https://codeforces.com/contest/1785/submission/192294893

불가능하다고 여긴 1)의 풀이. 비슷한 관찰은 했었는데 이 지점까지 도달하지 못하였다. (3안과 비슷하지만 살짝 더 복잡)

앞에서부터 순서대로 진행하여 a[i]가 새롭게 추가되며, 필요한 spell 1의 수인 cur의 변화를 생각해보자.

3가지 정도의 일이 일어날 수 있다.

i) 계단에 어떠한 변화도 생기지 않고, a[i]를 굳이 spell 1으로 줄일 필요가 없다. -> cur += a[i] - a[i]

ii) a[i]가 추가됨으로 인해 계단이 현재 m칸에서 한 칸 늘어난다. -> cur += a[i] - (m + 1)

iii) a[i]가 계단에 사용되긴 하지만 계단의 m칸으로 유지된다. -> cur += a[i] - x

    -> x는 a[i]가 계단에 사용되면서 더 이상 계단에 관여하지 않는 a[j]이다.

    -> 이때 반드시 a[j]는 계단에서 a[j]로 사용되었을 것이다. (그렇지 않다면 a[j]가 계단에서 a[j] 역할을 맡으면 됨)

    -> 따라서 x는 a[i]보다 크거나 같은, a[j]가 a[j]로 쓰이는 제일 작은 값일 것이다.

i, ii, iii의 식 형태가 모두 비슷하다.

    -> 만일 a[i]가 a[i]로 쓰이고 있으면 a[i]보다 크거나 같은 a[j]가 a[j]로 쓰이는 제일 작은 값은 a[i]이다. (i)

    -> 만일 iii에 해당하는 x가 존재하지 않는다면 계단의 칸 수 증가로 여길 수 있다. (ii)

    -> x만 구해줄 수 있다면 i, ii, iii를 동시에 모두 cur += a[i] - x 비슷하게 계산할 수 있다.

따라서 적당한 set<int> s = {k | k가 계단에서 감소 없이 쓰이고 있음}을 구해주면 충분하다.

    -> 만일 [1, i]에서 k가 계단에서 감소없이 쓰인다면 [1, i + j]에서도 k는 계단에서 감소 없이 사용된다.

    -> 따라서 최초로 k가 계단에서 감소없이 쓰이는 index를 구해주면 된다.

    -> 계단을 이루는 index들을 모은 집합을 stairs라고 하자.

    -> 제일 작은 숫자부터 stairs에 하나씩 index를 넣는다. (a[i] = j라면 i를 넣는다)

    -> 이때 만일 stairs.size() > j 라면 제일 큰 index부터 뽑는다.

    -> stairs.size() == j가 되었을 때 이중에서 제일 큰 index가 곧 우리가 원하는 최초의 index를 의미하게 된다.

 

D. Wooden Spoon

 

대충 N = (1 << n)인 문제라고 생각을 하면 dp식을 세워서 O(N^2)에는 어렵지 않게 풀 수 있다.

n = i일 때의 결과가 a, n = i + 1일 때의 결과가 b라면 a를 이용해서 b를 구하는 것이 가능하기 때문이다.

b[x] = (내가 있는 쪽을 결정하는 경우의 수) * (반대편을 정하는 경우의 수) * (좌우반전)

      =  sum(내가 있는 쪽에서 내가 j번째 크기인 경우의 수) * (반대편을 정하는 경우의 수 = (2^i)! ) * 2 

      =  sum(a[j] * C(x - 2, j - 1) * C(2^(i + 1) - x, 2^i - j)) * (2^i)! * 2

 

솔직히 식의 꼬라지를 잘보면 i, x, j에 의해서 식이 변화무쌍하게 바뀌는 거처럼 생겨서 각종 변형을 하다 실패.

아니 근데 이게 실제로는 식정리가 잘 되어 FFT가 된다고 한다.

일단 당연히 b[x]를 구하는데 오직 x에만 의존하는 부분인 분자를 떼어내자.

떼어내고 나면 분모에 (j - 1)! (x - j - 1)! (2^i - j)! (2^i - x + j)!이 남는다.

이부분이 얼핏보면 변수가 3개나 들어간 무가치한 부분처럼 보이지만

x - j = j'으로 치환하면  (j - 1)! (j' - 1)! (2^i - j)! (2^i - j')! 이 되어서 j + j' = x인 j와 j'에 대한 식이 된다.

그러면 이제는 FFT로 할 수 있겠다. (물론 개같이 NTT를 써야하긴 함)

 

절대 못 풀 문제가 아니라 식정리 실패로 못푼거라 좀 열받는다.