-
AtCoder Regular Contest 075 C Meaningful Mean 풀이
문제 요약 문제 링크 $N$개의 수가 있다. $i$번째 수를 $a_i$라 하자. 수열 $a$의 $N$개의 수에서 연속한 수들을 고르는 방법의 가지수는 $\frac{N \times (N+1)}{2}$ 개이다. $\frac{N \times (N+1)}{2}$ 개 중에서 평균이 $K$ 이상인 것이 몇개인지 구하라. $ 1 \le N \le 2 \times 10^5, 1 \le K \le 10^9, 1 \le a_i \le 10^9 $ 풀이 1. $O(N^3)$ Naive 한 방법. $\frac{N \times (N+1)}{2}$ 개의 모든 경우에 대해서, 직접 합을 구하고 평균이 $K$ 이상인지를 확인한다. 2....
-
AtCoder Grand Contest D Median Pyramid Hard 풀이
문제 요약 문제 링크 $N$층의 피라미드가 있다. $i$번째 층에는 $2i - 1$개의 칸이 있다. 피라미드의 $N$층에 $1, 2, \cdots, 2N-1$을 적절히 섞은 순열이 쓰여 있다. $1$층 부터 $N-1$층 까지의 칸에 숫자를 채우는 규칙은, 그 칸에 있는 수가 그 칸 아래쪽에 있는 $3$개의 수의 중앙값이라는 것이다. 위 방법에 따라 피라미드를 채웠을 때, $1$층에 있는 칸에 쓰인 숫자를 구해라. $ 2 \le N \le 10^5 $ 풀이 1. $O(N^2)$ 규칙에 맞춰서 모든 칸의 값을 구해본다. 공간복잡도가 $O(N^2)$라고...