Educational Codeforces Round 142

https://codeforces.com/contest/1792

 

A. GamingForces

 

누가봐도 체력이 큰 애들은 단번에 죽이는게 더 이득이다.

따라서 일단은 정렬을 해준다.

그 후 1번부터 i번까지는 1씩 줄이기를 사용하고, i + 1번부터 n번까지는 단번에 죽이는 비용을 모두 계산한다.

 

사실 단번에 죽이는 방법이 극단적으로 너무 이득이다.

엄밀하게 안 따져봐도 체력이 2 이상인 애들은 단번에 죽이는게 이득이다.

따라서 체력에 1인 애들의 개수를 세서 얘네만 1씩 줄이는 방법으로 죽여도 된다.

 

B. Stand-up Comedian

 

입출력과 제한조건만 봐도 a1, a2, a3, a4을 이용해서 답을 구하는 식을 만들 수 있을 거란 생각이 든다.

당연히 type 1을 제일 처음 모두 진행하고 최대한 가능한 만큼 type 2, 3를 번갈아 진행시키고 마지막에 4를 진행하면 된다.

 

C. Min Max Sort

 

operation을 진행한 애들은 무조건 제일 앞/뒤로 움직이게 된다.

그렇다면 가운데 쪽에 있는 애들은 operation을 안 받았다고 추론할 수 있다.

따라서 가운데에 처음부터 순서가 맞았던 애들의 수가 최대한 많도록 하면 된다.

가운데에 [i, i + 1, i + 2, ... j]가 처음부터 이 순서대로 있었다고 하자. 그렇다면 max(i - 1, n - j) 만큼의 operation이 든다.

-> 간단하게 투 포인터로 모든 i에 대해서 순서대로 있는 최대의 j를 편하게 구할 수 있다.

 

D. Fixed Prefix Permutations

 

m의 제한이 10으로 꽤 작기 때문에 여러가지 방법이 나올 수 있다.

inv된 순열로 트라이를 만들어서 앞에서부터 q[p[1]] = 1이 되는 q가 있는지,  q[p[2]] = 2가 되는 q가 있는지 확인한다.

 

E. Divisors and Table

 

깊게 생각하기가 귀찮아서 폴라드로를 들고 와서 단박에 m의 모든 약수를 다 구해버렸다.

t = 10이라서 폴라드 로 + 단순하게 약수 모두 구해버리기가 통할 거라고 생각했다.

그 다음에야 뭐 한 수의 약수들이다 보니 약수 집단 내에서만 a값들이 나올 것이니 하나하나 체크했다.

 

대회중에는 혹시 몰라서 set을 이용해서 적당히 숫자가 커지면 break하고 a가 나오면 삭제해서 조금 최적화했다.

너무 대충구현하면 (약수의 개수)^2 다 보니 일반적으로 (m^(1/3))^2로 TLE가 날 것이기 때문이다.

 

솔직히 풀이가 조금 개판이라서 진짜 풀이를 찾아봤다.

풀이에서도 걍 m1과 m2의 약수를 각각 구해서 곱하는걸 보니까 약수 구하는 것은 핀트를 벗어나지 않은 것 같고

a를 구하는 과정을 엄밀하게 했다.

d = xy이며 동시에 y <= n 인 최소의  x <= n을 구하는 것이므로 각 d에 대해서 n 이하의 최대의 y를 구해주어도 된다.

만일 d <= n 이라면 y(d) = d로 간단하게 구할 수 있다.

만일 아니라면 y(d) <= n < d 이고 y(d)는 y의 약수이므로 y(d) = max( y(d/p) ) 이다.

-> 따라서 작은 것부터 순차적으로 y(d)를 구해가면서 y(p * d) = max(y(p * d), y(d))를 해주면 된다.

-> 제아무리 1e18이더라도 소수의 개수는 20개를 넘지 못할거기에 (약수의 개수) * 20 * log가 될 것 같다.

-> 예상 복잡도가 그러면 1e6 * 20 * 30 정도인데 쪼오금 그런거 같다.

 

F. Graph coloring 

 

Claim) 모든 S는 적어도 두 색 중에 하나로는 connected가 반드시 된다.

-> pf) 수학적 귀납법을 쓰면 간단히 보일 수 있다.

 

전체에 대해서 red-connected라고 치자. (나중에 *2를 해줄 생각을 하는 중)

그러면 blue-connected인 지역들끼리 n개의 점들을 그룹지을 수 있다.

1번 점이 자신 포함 i개의 점과 blue-connected라고 치자. (대충 C(n - 1, i - 1)를 곱해줄 생각을 하는 중)

그러면 뭔가 딱봐도 n = i인 문제상황과 거의 일치함을 알 수 있다.

-> 즉, 서로 blue로 연결이 보장된 i개와 연결이 보장되지 않은 n - i개의 숫자를 구해서 곱해주면 답이 나올 것이다.

-> 전자를 a(i), 후자를 b(n - i)라고 하고 편의를 위해 all blue, all red도 마지막에 제외시키자. (editorial과 반대임에 유의)

-> 그러면 a(n) = sum( C(n - 1, i - 1) * a(i) * b(n - i) ) (i =2, 3, ... n - 2)임을 알 수 있다.

-> b(n) = 2 * a(n) (왜냐하면 blue-connect인지 red-connected인지 알 수 없음). 단, b[1] = 1, a[1] = 1

 

위의 것을 단순 구현하면 O(n^2)이 된다.

 

sol1)

하지만 식의 형태를 잘 보면 a가 마치 두 다항식의 곱처럼 보인다는 것을 볼 수 있다.

a(n) = sum( (n-1)! / (i - 1)! / (n - i)! * a(i) * b(n - i) ) 이다.

따라서 c(i) = a(i) / (i - 1)!   d(i) = b(i) / i!이라고 한다면 

a(n) = (n-1)! * sum( c(i) * d(n - i) ) 로 정리됨을 알 수 있다.

-> 그러면 (c(0) + c(1)x + ... + c(n)x^n) * (d(0) + d(1)x + ... + d(n)x^n) = e(0) + e(1)x + ... + e(n*2)x^(n*2) 이다.

-> i <= n + 1 이라면 e(i) * (i - 1)! = a(i)이지만 i > n + 1이라면 그렇지 않다!

-> 애초에 c(0)부터 c(n)까지 아는 상태에서 무려 nlgn인 FFT를 써서 겨우 (n + 1)번 항하나 구했다는 것은 이상하다.

-> 제대로 된 n + i 번째 항을 구하려면 n + 1, n + 2... n + i - 1번째 항을 추가로 더해줘야 한다.

그러면 n + 1항부터 n + k항까지 구하는데 nlgn (FFT) + k^2 (추가로 더해주기)의 계산이 필요하다.

k개씩 n/k번 구하면 되므로 총 n^2lgn/k + nk가 필요하고 적당한 k를 고르면 시간 내에 된다.

 

sol2) 

"After a careful examination" + 수학수학

Jiangly가 정확히 이렇게 했는지는 모르겠지만 main함수 내가 이런 느낌으로 엄청 간단해보인다.