結果

問題 No.2221 Set X
コンテスト
ユーザー limbo
提出日時 2025-12-02 04:51:41
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 2,520 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 741 ms
コンパイル使用メモリ 78,288 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-02 04:51:45
合計ジャッジ時間 4,253 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int N;
    if (!(cin >> N)) return;

    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // 1. Establish a Baseline
    // If X=1, we cover every distinct position individually.
    // Cost = N * (1 + 1) = 2N.
    long long min_cost = 2LL * N;
    long long best_X = 1;

    // 2. Determine Search Range
    // If X > 2N, the cost for a single segment (X + 1) exceeds our baseline (2N).
    // Therefore, optimal X must be <= 2N.
    // We also don't need to check X larger than the last element + padding.
    long long limit = 2LL * N;
    if (!A.empty()) {
        long long last_pos = A.back();
        // If the last position is small, we don't need to check up to 2N
        limit = min(limit, last_pos + 2); 
    }

    // 3. Iterate candidate widths X
    for (long long X = 1; X <= limit; ++X) {
        
        long long current_segments = 0;
        int idx = 0; // Pointer to current projectile index in A
        bool possible = true;

        // "Jump" Simulation
        while (idx < N) {
            current_segments++;
            
            // Optimization (Pruning):
            // If partial cost already exceeds the global minimum, stop immediately.
            // This turns the complexity from O(N^2) to O(N log N).
            if (current_segments * (X + 1) > min_cost) {
                possible = false;
                break;
            }

            // The current segment starts covering at A[idx].
            // Because the grid is rigid [0, X), [X, 2X)...
            // The segment containing A[idx] ends at: floor(A[idx]/X + 1) * X
            long long boundary = ((long long)A[idx] / X + 1) * X;

            // Use binary search (lower_bound) to skip all projectiles 
            // that fall inside this current segment.
            // We jump directly to the first projectile >= boundary.
            auto it = lower_bound(A.begin() + idx, A.end(), (int)boundary);
            idx = it - A.begin();
        }

        if (possible) {
            long long total_cost = current_segments * (X + 1);
            if (total_cost < min_cost) {
                min_cost = total_cost;
                best_X = X;
            }
        }
    }

    cout << best_X << "\n" << min_cost << "\n";
}

int main() {
    // Fast I/O for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    solve();
    
    return 0;
}
0