[BOJ] 백준 15976. XCorr (Gold III)

백준 초급스터디에 과제로 내준 문제인데, 생각보다 어려워보이는 문제여서 한 번 풀어보았다.

KOI (정보올림피아드) 2018 고등부 2번 문제이기도 하다.

일단 비주얼부터 한 번 감상해보자.

비주얼이 거의 수능수학 문제를 뺨친다.

문제는 아래와 같다.

https://www.acmicpc.net/problem/15976

15976번: XCorr

문제가 조금 헷갈릴 수 있는데, 입력에 주어지지 않은 xi, yi는 0이라고 생각하면 된다.

---

의식의 흐름 및 해설

우리가 구하려는 것을 다시 한 번 살펴보자.

으... 정말 비주얼이 끔찍하다. 일단 a, b가 - 10^9 ~ 10^9이다.

물론 N, M이 30만까지이긴 하지만, n, a, b의 범위가 너무나도 끔찍하다.

그렇기 때문에 우리는 N, M을 적극 활용할 수 있도록 해야 한다. 잘 생각해보면 index의 범위는 10억까지이지만, 막상 들어오는 개수는 30만개까지이므로 좌표압축을 해야겠다는 생각을 할 수 있다.

 

그리고 예제입력2 의 답을 구해지는 과정을 한 번 적어보면 아래와 같다.

잘 생각해보면 y는 a, b의 범위에 따라서 특정 구간 [i+a, i+b]의 누적합만 식에 이용됨을 알 수 있다.

따라서 y의 누적합을 구해준 후, xi가 양의 정수일 때마다 [i+a, i+b] 구간의 y의 누적합을 곱해주는 방법으로 해결해줄 수 있다.

좌표압축을 해주었기 때문에 [i+a, i+b] 구간을 이분탐색으로 O(lgM)에 구해주어야 하므로 시간복잡도는 O(NlgM)이다.

---

코드

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int,pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 3e5+7;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
ll N,M,A,B,p[MAX],ans;
vector<ll> x,y,X,Y;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>N;
    X.push_back(0);
    for(int i=0;i<N;i++){
        ll idx,val;
        cin>>idx>>val;
        x.push_back(idx);
        X.push_back(val);
    }
    cin>>M;
    Y.push_back(0);
    for(int i=0;i<M;i++){
        ll idx,val;
        cin>>idx>>val;
        y.push_back(idx);
        Y.push_back(val);
    }
    for(int i=1;i<=M;i++){
        p[i]=p[i-1]+Y[i];
    }
    cin>>A>>B;
    for(int i=0;i<N;i++){
        ll s=lower_bound(all(y), x[i]+A)-y.begin();
        ll e=upper_bound(all(y), x[i]+B)-y.begin();
        ans+=X[i+1]*(p[e]-p[s]);
    }
    cout<<ans;
}

---

요즘 감이 좀 떨어졌는데, 이 문제 덕분에 이분탐색, 누적합 감을 조금이나마 살릴 수 있었다.

골드3 치고는 좀 어려운 느낌? 도 없잖아 있는 듯.

나는 골드2에 투표했다.