백준27490 Moving Dots

작성일 | In

문제 링크

  • http://icpc.me/27490

사용 알고리즘

  • 더블 카운팅

시간복잡도

  • $O(N^2 \log N)$

풀이

점의 이동 방향이 중간에 바뀌지 않는다는 것을 먼저 관찰해야 합니다. 그림을 몇 번 그려보면 어렵지 않게 증명할 수 있습니다.
따라서 두 점 $X_i$와 $Y_j$가 만나서 하나의 점을 이룰 조건은 $X_i$와 $X_j$가 서로 가장 가까운 두 점이 되어서 두 점의 중점에서 만나는 것임을 알 수 있습니다.

더블 카운팅을 합시다. 즉, 모든 부분 집합에 대해 점의 개수를 구하는 것 대신, 각 점이 등장하는 부분 집합의 개수를 셀 것입니다.
$u$에 있는 점과 $v$에 있는 점($u < v$)이 만나게 되는 부분 집합의 수를 구합시다. 이는 $[2u-v, 2v-u)$ 구간에 포함되지 않는 점들의 집합의 부분 집합의 개수와 동일합니다. 따라서 구간에 포함되지 않은 점의 개수를 이분 탐색으로 구한 뒤, 2의 거듭제곱 꼴을 계산해서 정답에 더하면 됩니다.

더블 카운팅이라는 키워드만 떠올릴 수 있다면 어렵지 않게 풀 수 있는 문제입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9+7;

ll N, A[3030], P[3030], R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    P[0] = 1; for(int i=1; i<3030; i++) P[i] = P[i-1] * 2 % MOD;
    cin >> N; for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            int cnt = upper_bound(A, A+N, 2*A[j]-A[i]-1) - lower_bound(A, A+N, 2*A[i]-A[j]);
            R += P[N-cnt]; if(R >= MOD) R -= MOD;
        }
    }
    cout << R;
}