1540A Great Graphs

$d_1, d_2, \cdots, d_n$을 크기 순서대로 정렬하자. 모든 $i < j$에 대해 $j$에서 $i$로 향하고 비용이 $d_i - d_j$인 간선을 추가하고, $1$에서 $n$으로 향하고 비용이 $d_n$인 간선을 추가하였다고 하자. 이때 음수 비용 사이클은 존재하지 않고, 또한 $1 \to n \to i$와 같은 경로를 통해 모든 정점 $i$에 대해 주어진 $d_i$을 최소비용으로 사용하여 $i$에 도착할 수 있다.

한편, 음수 비용 간선을 더 추가할 수 없다. $i < j$에 대해 $i \to j$ 방향 음수 간선을 추가한다면 $d_i \le d_j$에 모순이다. $j \to i$ 방향 음수 비용 간선에서 비용의 절대치를 늘릴 수 없는데, $i$까지 도달하는데의 최소 비용이 항상 $d_j + (d_i - d_j) = d_i$보다 작아지고 이는 모순이다.

양수 비용 간선의 비용 합은 조건에 의해 적어도 $d_n$이어야 한다. 따라서 위 구성은 농장의 비용을 최소화하고, 이 비용이 원하는 답이 된다. $\displaystyle\sum_{i < j} (d_i - d_j) = \sum_{i = 1}^n (n - 1 - 2i) d_i$를 계산하고 여기에 $d_n$을 더하면 원하는 답이다. 정렬하는데 사용된 시간은 $\mathcal{O}(n \log n)$이고, 원하는 답을 계산하기 위해 $\mathcal{O}(n)$만큼의 시간을 사용한다.

1540B Tree Array

뿌리 정점을 하나 고정하였을 때, 모든 $1 \le i < j \le n$에 대해 $j$가 $i$보다 먼저 등장할 확률 $p_{ij}$을 계산하여 합 $\displaystyle\sum_{i < j} p_{ij}$을 구하면 이는 이 뿌리 정점에 대해 나타날 수 있는 모든 tree array에서 나타나는 반전^inversion 개수의 기댓값이다. 구한 $N$개의 합의 평균이 원하는 답이 된다.

$p_{ij}$는 $i$와 $j$의 최소 공통 조상에 대한 상대 깊이에만 의존한다. $i$와 $j$를 연결하는 경로 위에 있지 않은 정점들을 선택하는 순서는 $i, j$ 사이의 순서에 영향을 주지 않기 때문이다. $i, j$의 상대 깊이를 각각 $x, y$라고 하자. 이때 반전 개수의 기댓값을 $F(x, y)$라고 할 때, 다음 점화식을 얻을 수 있다. $F(0, n) = 0, F(m, 0) = 1, F(x, y) = \frac{1}{2} F(x - 1, y) + \frac{1}{2} F(x, y - 1)$ 이는 메모이제이션으로 $\mathcal{O}(N^2)$ 시간안에 전처리 후 $\mathcal{O}(1)$ 시간을 사용해서 결과를 얻을 수 있다. $\mathcal{O}(N^2)$개의 $i < j$ 쌍에 대해 최소 공통 조상을 구하는 데에 $\mathcal{O}(\log N)$ 시간이 사용되고, 이를 $N$개의 정점에 대해 그를 뿌리로 고정하여 반복하므로 전체 답을 구하는 데에 $\mathcal{O}(N^3 \log N)$ 시간이 사용된다.

한편, 최소 공통 조상을 매번 계산하여야 해서 로그 항이 곱해진다. 전처리를 통해 $i < j$쌍에 대해 최소 공통 조상을 $\mathcal{O}(1)$ 시간 복잡도로 계산할 수 있으므로 $p_{ij}$는 메모이제이션 이후 $\mathcal{O}(1)$ 시간 복잡도로 계산할 수 있다. 따라서 $\mathcal{O}(n^3)$ 시간 복잡도 풀이도 존재한다.