C. Chain Reaction

rmq, binary search, dp

출처: Codeforces C. Chain Reaction

SOL)
d 배열에는 d[pos] 현재 위치 pos에서 기계를 작동하면
앞에 놓인 beacon이 몇개 파괴되는지를 기록한다.
예를 들어 beacon이 (1,1), (2,1), (6,1), (7,1)이 있다면
d[7] = 2가 기록된다. (1,1)은 (2,1)에게 (6,1)은 (7,1)에게
파괴된다.

그렇다면 우리는 현재위치 pos에서 과연 이 beacon이
어디까지 영향을 미치는지 알아내고
그 알아낸 위치 바로 왼쪽에 놓인 녀석이 작동했을때
몇개를 파괴하는지 더해주면 된다.

여기서 요것들을 빠르게 알아내기 위해서 가장 왼쪽에
놓인 beacon부터 테이블을 채워나가고
어디까지 영향을 미치는지 빠르게 알아내기위해
이분법, 또는 rmq를 사용한다.

그리고 마지막에 새로놓이는 마지막 beacon으로 아무것도
파괴하지 않는경우 부터해서 차례대로 i번째 녀석을 파괴했을때를
고려하여 최소값을 찾아낸다.


[-] Collapse

#include<stdio.h>
#include<algorithm>
using namespace std;

pair<int, int> ele[100010];
int d[1000010];
int n;

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d %d", &ele[i].first, &ele[i].second);

    sort(ele + 1, ele + n + 1);

    for (int i = 2; i <= n; i++){
        int s = 1, e = i - 1, mid;
        int pos = ele[i].first;
        int power = ele[i].second;
        int rv = i;
        while (s <= e){
            mid = (s + e) / 2;
            if (ele[mid].first >= pos - power){
                rv = mid;
                e = mid - 1;
            }
            else{
                s = mid + 1;
            }

        }
        d[pos] = d[ele[rv-1].first] + i - rv;
    }

    int ans = d[ele[n].first];
    for (int i = 1; i <= n; i++){
        ans = min(ans, d[ele[i - 1].first] + n - i + 1);
    }
    printf("%d\n", ans);

    return 0;
}

[-] Collapse

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define mp make_pair
int n, h = 1;
int T[4 *1000100];
int dstry[1000010];

vector <pair<int, int>> ele;
int query(int l, int r){
    int ans = 0;
    while (l <= r){
        if (l & 1) ans += T[l];
        if (!(r & 1)) ans += T[r];
        l = (l + 1) >> 1;
        r = (r - 1) >> 1;
    }
    return ans;
}
int main(){
   // freopen("input.txt", "r", stdin);
    memset(T, 0, sizeof(T));
    int w, s;
    scanf("%d", &n);
    int mx = 0;
    for (int i = 0; i < n; i++){
        int pos, power; scanf("%d %d", &pos, &power);
        ele.push_back(mp(pos, power));
        mx = max(mx, pos);
    }
    sort(ele.begin(), ele.end());
    while (h < mx + 1) h <<= 1;
    for (int i = 0; i < n; i++){
        int pos = ele[i].first;
        int power = ele[i].second;
        T[pos + h] = 1;
    }
    for (int i = h - 1; i >= 1; i--) T[i] = T[i * 2] + T[i * 2 + 1];

    for (int i = 0; i < n; i++){
        int pos = ele[i].first;
        int power = ele[i].second;
        int v = query(h+max(0, pos - power), h+pos - 1);
        dstry[pos] = v;
        if (i - v -1 > 0){
            dstry[pos] += dstry[ele[i - v-1].first];
        }
    }
    int val = n;
    for (int i = 1; i < n; i++){
        int pos = ele[i].first;
        int prev = ele[i - 1].first;
        int cal = n - (i + 1) + 1 + dstry[prev];
        val = min(val, cal);
    }
    printf("%d", min(dstry[ele[n-1].first], val));
    return 0;
}