Problem info
| Title | Codeforces Round 975 |
| Division | Div.2 |
| Problem | B. All Pairs Segments |
Try
| # | Verdict | Time |
|---|---|---|
| 1 | WA on 9 | +64 |
| 2 | Accept | +67 |
풀이방식
$n, q$가 최대 $10^5$이기 때문에, $O(n^2)$은 불가능하다.
$x_i (1 \leq i \leq n)$ 는 오름차순으로 정렬되어 있고, 같은 값을 가지는 수가 존재하지 않기 때문에 segment $[a, b]$사이에 있는 값은$a, a+1, …, b$밖에 없다. 그리고 모든 가능한 조합을 만들어 보면 쉽게 풀 수 있다.
example
$n = 4$일 때 존재할 수 있는 모든 segment의 index 쌍은
[1, 2], [1, 3], [1, 4]
[2, 3], [2, 4]
[3, 4]
여기서 규칙성을 잘 찾아보면
1번과 4번는 3회만 나타난다.
1~2 사이의 수 (1과 2 제외)는 3회만 나타난다.
2번은 3 (1번이 나타나는 개수) + 2 = 5회 나타난다.
2~3 사이의 수 (2와 3 제외)는 5 (2번이 나타나는 개수) - 1 = 4
(2번이 나타나는 개수 중 [1, 2]는 2~3사이에 있는 값이 나타날 수 없다.)
이런식으로 생각해 보면 각각의 $x_i$들과 그 사이에 있는 값들로 나눠서 생각하면 규칙을 찾을 수 있다.
Solution
$1…n$만큼 반복문을 돌면서 각 index마다 다음과 같은 작업을 수행한다.
- 이전에 더했던 값을 가져와서 $n-i-1$만큼 더한다.
- 이전에 사용했던 값과 $i$가 $index$인 값 ($j$가 $index$보다 커야하기 때문에 $n-i$)만큼 더한다.
- 계산한 만큼의 갯수를 가지는 $result$를 1만큼 더해준다.
- $index$ 본인에 관한 것
- 계산한 값에 다시 $index-1$만큼 뺀다.
- $j$가 $index$인 segments는 더이상 계산하지 않는다.
- 계산한 값의 갯수를 가지는 $result$를 $x_{index+1} - x_{index} - 1$만큼 더해준다.
- $index$를 제외한 $index$와 $index+1$사이에 있는 값들을 계산한다.
- 다 계산 후 마지막 index를 계산해준다.
Time complexity: $O(n)$
Attempt 1
Integer overflow Issue!!!!!!!!!
계산하는 값이 int범위를 넘을 수 있기 때문에 (최대 $\sum_{i=1}^{n} i$) long long으로 선언해야 한다.