AtCoder ABC 318 F - Octopus (黄色, 575 点)

高速な解法もあるっぽいけど、愚直に解いた。

• 問題へのリンク

問題概要

一直線上に 個の宝が座標 に配置されている。一方、長さが である 本の棒がある。次の条件を満たす整数 の個数を求めよ。

---

各 に対して、座標 の点を始点とするように棒を置いたとき、棒が宝を含むとき、それらの宝を選んで取り除いていくことを繰り返したとき、宝をすべて取り除くことができる。

---

制約

• 

考えたこと

この手の問題では、ギリギリの点を列挙するのが定石だと思う。そうした点と点の間にある座標については、「常に条件を満たす」「常に条件を満たさない」のいずれかになる感じになる。

ここでは、各 に対して、 らが候補点となる。つまり、候補点は 個ある。それぞれの候補点、および間の点たちについて、 Greedy で で判定できる。

よって全体として の計算量となる。

高速な解法

各 i=1,2,...,N について、「k-L_i <= x <= k+L_i の範囲に宝が i 個以上」あればよい。i についての条件は、「k が含む区間 [X_j-L_i, X_j+L_i] が i 個以上ある」と言い換えられる。X_j-L_i, X_j+L_i をソートして座圧して、各 i について区間の個数を管理しながら平面走査する。

— SSRS (@SSRS_cp) 2023年9月2日

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> X(N), L(N);
    for (int i = 0; i < N; ++i) cin >> X[i];
    for (int i = 0; i < N; ++i) cin >> L[i];
    
    vector<long long> alt;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            alt.push_back(X[i] - L[j]);
            alt.push_back(X[i] + L[j]);
        }
    }
    const long long INF = 1LL<<62;
    alt.push_back(-INF);
    alt.push_back(INF);
    sort(alt.begin(), alt.end());
    alt.erase(unique(alt.begin(), alt.end()), alt.end());
    
    auto check = [&](long long x) -> bool {
        vector<long long> dis;
        for (int i = 0; i < N; ++i) dis.push_back(abs(x - X[i]));
        sort(dis.begin(), dis.end());
        for (int i = 0; i < N; ++i) if (dis[i] > L[i]) return false;
        return true;
    };

    long long res = 0;
    for (int i = 0; i+1 < alt.size(); ++i) {
        if (check(alt[i])) ++res;
        if (check((alt[i] + alt[i+1])/2)) res += alt[i+1] - alt[i] - 1;
    }
    cout << res << endl;
}