結果

問題 No.705 ゴミ拾い Hard
ユーザー drken1215
提出日時 2025-04-10 01:50:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 332 ms / 1,500 ms
コード長 4,431 bytes
コンパイル時間 3,849 ms
コンパイル使用メモリ 291,312 KB
実行使用メモリ 22,912 KB
最終ジャッジ日時 2025-04-10 01:51:00
合計ジャッジ時間 11,423 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

//
// 一般化 Convex Hull Trick
//    Monge 性を満たす関数群 f_1, f_2, ..., f_N
//
// verified
//   COLOCON 2018 Final C - スペースエクスプローラー高橋君
//     https://beta.atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c
//
//   AtCoder EDPC Z - Frog 3
//     https://atcoder.jp/contests/dp/tasks/dp_z 
//
//   yukicoder No.705 ゴミ拾い Hard
//     https://yukicoder.me/problems/no/705 
//


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


// Convex Hull Trick
/*
    Func：Monge 性を仮定
    - MIN: クエリ x の取りうる最小値
    - MAX: クエリ x の取りうる最大値 (f_i(MAX) がオーバーフローしないように注意）
    - INF: 最大値
 
    - insert (Func f_i): add f_i, O(log N)
    - query (x): min_i{ f_i(x) }, O(log N)
*/
template<class T> struct CHT {
    using Func = function<T(T)>;
    struct Node {
        Func func;
        Node *left, *right;
        Node(const Func& f) : left(nullptr), right(nullptr) {
            func = f;
        }
    };
    
    const T MIN, MAX, INF;
    Node* root;
    
    CHT(T MIN, T MAX, T INF) : MIN(MIN), MAX(MAX), INF(INF), root(nullptr) { }
    Node* insert(Node* p, T low, T high, Func& f) {
        if (!p) return new Node(f);
        if (p->func(low) <= f(low) && p->func(high) <= f(high)) return p;
        if (p->func(low) >= f(low) && p->func(high) >= f(high)) {
            p->func = f;
            return p;
        }
        T mid = (low + high) / 2;
        if (p->func(mid) > f(mid)) swap(p->func, f);
        if (p->func(low) >= f(low)) p->left = insert(p->left, low, mid, f);
        else p->right = insert(p->right, mid, high, f);
        return p;      
    }
    void insert(Func f) {
        root = insert(root, MIN, MAX, f);
    }
    T query(Node* p, T low, T high, T x) {
        if (!p) return INF;
        if (low == high) return p->func(x);
        T mid = (low + high) / 2;
        if (x <= mid) return min(p->func(x), query(p->left, low, mid, x));
        else return min(p->func(x), query(p->right, mid, high, x));
    }
    T query(T x) {
        return query(root, MIN, MAX, x);
    }
};



//------------------------------//
// Examples
//------------------------------//

// COLOCON 2018 Final C - スペースエクスプローラー高橋君
void COLOCON_2018_final_C() {
    long long N;
    cin >> N;
    vector<long long> a(N), res(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    CHT<long long> cht(0, 210000, 1LL<<60);
    for (long long i = 0; i < N; ++i) {
        auto func = [i, &a](long long x) -> long long { return (x - i) * (x - i) + a[i]; };
        cht.insert(func);
    }
    for (long long i = 0; i < N; ++i) res[i] = cht.query(i);
    for (int i = 0; i < N; ++i) cout << res[i] << endl;
}

// AtCoder EDPC Z - Frog 3
void EDPC_Z() {
    long long N, C;
    cin >> N >> C;
    vector<long long> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];

    const long long INF = 1LL<<60;
    const long long MAX = 1LL<<40;
    vector<long long> dp(N, INF);
    /*
    　　dp[i] = min_j(dp[j] + (H[j] - H[i])² + C)
    */
    dp[0] = 0;
    CHT<long long> cht(0, MAX, INF);
    auto func = [&H, C](long long x) -> long long {
        return (x - H[0]) * (x - H[0]) + C;
    };
    cht.insert(func);
    for (int i = 1; i < N; i++) {
        long long val = cht.query(H[i]);
        dp[i] = min(dp[i], val);
        auto func = [&dp, &H, i, C](long long x) -> long long {
            return (x - H[i]) * (x - H[i]) + dp[i] + C;
        };
        cht.insert(func);
    }
    long long res = dp[N-1];
    cout << res << endl;
}

// yukicoder No.705 ゴミ拾い Hard
void yukicoder_705() {
    int N;
    cin >> N;
    vector<long long> A(N), X(N), Y(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> X[i];
    for (int i = 0; i < N; i++) cin >> Y[i];

    const long long INF = 1LL<<60;
    const long long MAX = 110000;
    vector<long long> dp(N+1, INF);
    CHT<long long> cht(0, MAX, INF);
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        auto func = [&dp, &X, &Y, i](long long x) -> long long {
            long long dx = abs(x - X[i-1]), dy = abs(Y[i-1]);
            return dp[i-1] + dx*dx*dx + dy*dy*dy;
        };
        cht.insert(func);
        dp[i] = cht.query(A[i-1]);
    }
    cout << dp[N] << endl;
}


int main() {
    //COLOCON_2018_final_C();
    //EDPC_Z();
    yukicoder_705();
}
0