結果

問題 No.1467 Selling Cars
コンテスト
ユーザー Kanten4205
提出日時 2025-11-20 03:00:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,056 bytes
コンパイル時間 1,476 ms
コンパイル使用メモリ 97,592 KB
実行使用メモリ 50,896 KB
最終ジャッジ日時 2025-11-20 03:01:05
合計ジャッジ時間 12,250 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 定数
const long long INF = 1e18;

int M, N;
vector<long long> A, B;
vector<long long> ans;

// 累積コストテーブル
// SumDist[j][x] = sum_{p=0}^{x-1} |A[p] - B[j]|
// これにより区間コストが O(1) で求まる
vector<vector<long long>> SumDist;

// 手動Deque (定数倍高速化)
struct FastDeque {
    int* q_idx;
    long long* q_val;
    int head, tail;
    int capacity;

    FastDeque(int size) {
        capacity = size + 5;
        q_idx = new int[capacity];
        q_val = new long long[capacity];
        head = 0;
        tail = 0;
    }
    
    // デストラクタ等省略（競プロ用途）

    inline void clear() {
        head = 0;
        tail = 0;
    }

    inline bool empty() { return head == tail; }

    inline void push_back(int idx, long long val) {
        q_idx[tail] = idx;
        q_val[tail] = val;
        tail++;
    }

    inline void pop_back() { tail--; }
    inline void pop_front() { head++; }
    inline long long back_val() { return q_val[tail - 1]; }
    inline int front_idx() { return q_idx[head]; }
    inline long long front_val() { return q_val[head]; }
};

// 事前計算処理
void precompute_costs() {
    SumDist.assign(N, vector<long long>(M + 1, 0));
    
    // 各 B[j] に対して、A の全要素との距離の累積和を計算
    // A はソート済みなので、|A[p] - B[j]| の計算はポインタを進めながらやると速いが
    // ここは O(MN) かけて愚直にやっても全体に比べれば軽い
    for (int j = 0; j < N; ++j) {
        long long b_val = B[j];
        long long current_sum = 0;
        SumDist[j][0] = 0;
        for (int x = 1; x <= M; ++x) {
            current_sum += abs(A[x-1] - b_val);
            SumDist[j][x] = current_sum;
        }
    }
}

// 固定された容量 k に対する最小コスト計算
// 計算量: O(MN) だが定数倍が非常に軽い
long long calc(int k) {
    if (k <= 0) return INF;
    if (k > M) k = M;

    // 1次元DP配列 (prev -> curr)
    vector<long long> dp(M + 1, INF);
    dp[0] = 0;

    // バッファ
    vector<long long> next_dp(M + 1);
    
    // Deque (static にして再利用)
    static FastDeque dq(M + 5);

    for (int j = 0; j < N; ++j) {
        dq.clear();
        
        // SumDist[j] への参照 (ポインタアクセスの最適化を期待)
        const vector<long long>& S = SumDist[j];

        for (int x = 0; x <= M; ++x) {
            // 遷移: next_dp[x] = S[x] + min(dp[y] - S[y])  where x-k <= y <= x
            
            // 1. 新しい候補 (dp[x] - S[x]) を追加
            if (dp[x] != INF) {
                long long val = dp[x] - S[x];
                while (!dq.empty() && dq.back_val() >= val) {
                    dq.pop_back();
                }
                dq.push_back(x, val);
            }

            // 2. 範囲外 (index < x - k) を削除
            if (!dq.empty() && dq.front_idx() < x - k) {
                dq.pop_front();
            }

            // 3. 最小値で更新
            if (!dq.empty()) {
                next_dp[x] = S[x] + dq.front_val();
            } else {
                next_dp[x] = INF;
            }
        }
        dp = next_dp;
    }
    return dp[M];
}

// 分割統治
void solve_dc(int l, int r) {
    if (l + 1 >= r) return;

    int mid = (l + r) / 2;
    ans[mid] = calc(mid);

    // 傾きチェック (l, mid, r)
    // (y2 - y1) * (x3 - x2) == (y3 - y2) * (x2 - x1)
    long long dy1 = ans[mid] - ans[l];
    long long dx1 = mid - l;
    long long dy2 = ans[r] - ans[mid];
    long long dx2 = r - mid;

    // 傾きが一致していれば線形補間 (D&Cの枝刈り)
    if (dy1 * dx2 == dy2 * dx1) {
        long long slope = dy1 / dx1;
        for (int i = l + 1; i < r; ++i) {
            if (i == mid) continue;
            ans[i] = ans[l] + slope * (long long)(i - l);
        }
        return;
    }

    solve_dc(l, mid);
    solve_dc(mid, r);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> M >> N)) return 0;

    A.resize(M);
    for (int i = 0; i < M; ++i) cin >> A[i];
    B.resize(N);
    for (int i = 0; i < N; ++i) cin >> B[i];

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    // 1. コストテーブルの前計算
    precompute_costs();

    ans.resize(M + 1);

    // 2. 上限の探索 (k=M のときは Greedy と等価)
    // 実は k がある程度大きくなるとコストは下がらなくなる。
    // その境界を知るために k=M (無限扱い) を計算。
    // ただし実装簡易化のため、単に [1, M] で D&C を行う。
    // D&C の補間が効くため、後半が平坦なら高速にスキップされる。

    ans[1] = calc(1);
    ans[M] = calc(M);

    solve_dc(1, M);

    for (int i = 1; i <= M; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}
0