Codeforces Round 891 (Div. 3)

Dashboard - Codeforces Round 891 (Div. 3) - Codeforces

 

 

B

greedy 방법으로 낮은 자리수부터 보다가 반올림 할 수 있으면 하고, 그렇지 않으면 안하면 된다.

 

F

t² + xt + y = 0의 두 해가 ai, aj 임을 이용하는 문제다.

 

G

되게 흥미로운 문제였다. 결국에는 editorial을 보고 풀었다.
배경지식으로는 크루스칼 알고리즘이 필요하다. 

다음 관찰까지는 해냈다.

간선이 존재하지 않는 임의의 edge (u, v) 에 대해 u와 v를 연결하는 경로에서의 간선 가중치의 최대값을 w라고 하자.
그러면 edge (u, v)의 가중치는 0, w+1, w+2, ... , S 의 값을 가질 수 있다. (가중치가 0이면 없는 간선 취급).
즉, edge (u, v)는 (S-w+1)가지의 가중치를 가질 수 있다.

조건을 만족하는 그래프의 개수는 간선이 존재하지 않는 모든 edge (u, v) 각각의 (S-w+1) 곱이다.

이때 문제는 존재하지 않는 간선의 개수가 N² 에 bound 된다는 것이다. 따라서 w를 LCA로 여차저차 O(lg N)에 구해도 시간안에 문제를 해결할 수 없다.

아래 editorial에서는 좀 더 우아한 방법으로 이를 해결하고 있다.