Codeforces Round #783 (Div. 1)

https://codeforces.com/contest/1667

 

A. Make it Increasing

 

자명하게도, 어떤 지점을 0으로 설정하는 것이 제일 이득이다.

따라서 모든 n개의 지점에 대해 그 지점을 0으로 설정해두고, O(n)으로 각각의 경우가 최소 얼마가 가능한지 확인한다.

https://codeforces.com/contest/1667/submission/155759128

 

B. Optimal Partition

 

Naive dp : dp[i] = max(dp[j] + val[j+1][i]) (j + 1 <= i) 

어차피 max값만 보면 되고, prefix sum의 값에 따라서 val[j+1][i]가 i - j, 0, j - i 중 무엇인지 결정되므로 max segtree로

https://codeforces.com/contest/1667/submission/155761724

 

C. Half Queen Cover

 

Constructive로 할 수 있다.

오른쪽 귀퉁이에 x*x 정사각형을 만들어 두자.

그렇다면 n - x개의 Half Queen를 이용하여 오른쪽과 아래쪽의 x행과 x열을 제외한 나머지 행/열을 채운다고 생각하자.

그 후 n - x개의 대각선을 채우는 능력으로 x * x 정사각형을 채워주면 된다.

아래와 같은 방법으로 할 수 있다.

https://codeforces.com/contest/1667/submission/155764479

 

cf) '여러번 해보기'로 얻은 전략이라 이 전략을 어떻게 하면 더 빨리 얻을 수 있었을지는 모르겠다.

     딱 9X9까지 해보면서 얻은 전략이다.

 

D. Edge Elimination

 

버츄얼을 돌릴 때 D번의 constructive한 풀이와 E번의 Sum(Combination) 계산 중에서 E를 선택하였다.

생각한 것은 우선 건드리는게 불가능한 tree가 생겨나면 끝난다는 사실인데, 어떻게 이를 방지해야 할까...

 

Vertex의 홀짝성 : 인접한 Edge의 수의 홀짝성

Edge의 홀짝성 : 인접한 두 vertex의 홀짝성이 같을 때 그 vertex들의 홀짝성과 동일

-> 어떤 edge가 제거되면 양 옆 vertex의 홀짝성이 변화

-> 따라서 다음에 그 vertex들에서 제거되는 edge의 홀짝성은 이전 edge와 홀짝성이 다르다.

-> 따라서 어떤 vertex와 인전한 edge들은 짝수 edge가 절반, 홀수 edge가 절반이어야 한다.

-> 이 조건을 만족한다면 Edge Elimination은 무조건적으로 가능하다.

 

E. Centroid Probabilities

 

어차피 두 솔루션 모두 개수를 세는 수학이다.

sol1) (Kostka의 댓글 확인)

모든 트리는 1이 제일 앞에 있는 길이 n인 permutation과 대응시킬 수 있다.

예를 들어, (1, 3, 2, 4, 5)라면 (1, 2) (1, 3), (2, 4), (4, 5)가 있는 트리이다. (순서대로 insert될 때 내 바로 앞의 숫자와 연결)

하지만 i가 centroid인지를 확인할 때에는 1, 2, ... i의 연결 상태는 중요하지 않다. (어차피 같은 subtree에 있음)

-> 1, 2, 3, ... i는 고정해둔채로 permutation를 만들 수 있다.

만일 i에 대해서 i가 centroid가 되기 위해서는 i보다 작은 숫자들이 있는 subtree의 크기가 n/2보다 작거나 같아야 한다.

이는 i보다 작거나 같은 숫자들이 전부 n/2 이하의 포지션에 존재하는 것과 필요충분하다.

왜냐하면 i보다 작은 숫자들이 있는 subtree와 동일한 subtree에 존재하는 숫자들은 i보다 왼쪽에 존재해야하기 때문.

-> 그러면 이런 경우의 수는 (n-1)! * (C(n/2, i-1)/C(n-1, i-1))임을 알 수 있다.

하지만 이런 애들 중에는 i+1, i+2....이 centroid인 경우가 포함되어 있다.

-> 따라서 이미 저런 자리에서 subtree의 크기가 n/2보다 작아진 경우들을 제외하여야 한다.

(i+1, i+2....에서 이미 i + a이하가 n/2보다 작다면 당연하게도 i에서도 i - 1이하의 subtree는 n/2 이하가 된다.)

-> 그러면 i + 1, i + 2...가 i와 직접적으로 연결된 케이스만 제거해주면 된다.

중복되는 케이스는 없는가? 

i와 i+1, i+2가 연결된 트리가 있다고 가정하자.

만일 i + 1이 보았을 때 i가 있는 subtree가 n/2이하라 가정하자.

그렇다면 i가 보았을 때 i + 1이 있는 subtree의 크기는 n/2 이상이다.

따라서 i + 2가 보았을 때 i가 있는 subtree의 크기는 n / 2 + 1이상이므로 중복되는 경우가 있을 수 없다.

https://codeforces.com/contest/1667/submission/155809581

 

sol2)

editorial의 계산 참고. (Jiangly의 댓글 확인)

단, editorial은 마지막에 NTT를 사용하여 계산했지만, 실제로는 dp[i] = (n-i)!(i-1)!C(n-s, i-1)과 동일하다.

 

 

수학적인 계산을 할 때 다항식적으로 표현하는 것을 고려하기도 했다. (댓글에 있음)

그 접근을 빨리 버린 것은 현명했다.