-
kajebiii's profile image
kajebiii
September 17, 2019
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....
-
kajebiii's profile image
kajebiii
August 18, 2019
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)$라고...
-
kajebiii's profile image
kajebiii
July 17, 2019
2019 SCPC Round 2 5번 풀이
문제 요약 $M \times M$ 격자판에 $N$ 개의 점이 찍혀 있다. 각 점에 대해서, 그 점은 왼쪽 아래로 하는 가장 큰 정사각형을 그리려 한다. 단, 정사각형은 $N$ 개의 점중 어떤 점이라도 내부에 포함시키면 안된다. 모든 점에 대해서 정사각형을 그릴 때, 모든 정사각형 변의 합을 구하시오. $2 \le M \le 10^9$, $1 \le N \le 500000$ 풀이 1. 먼저 2D Range Tree 를 써서 특정 직사각형 구간에 점의 개수를 $O(\log^2 N)$ 시간에 알 수 있다. 여기에...