結果

問題 No.198 キャンディー・ボックス２
コンテスト
ユーザー bolero
提出日時 2025-12-11 20:01:40
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,528 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,469 ms
コンパイル使用メモリ 335,396 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-11 20:01:48
合計ジャッジ時間 7,246 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR(i, s, e) for (long long i = (long long)(s); i <= (long long)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

long long op(long long a, long long b)
{
    return a + b;
}

long long e()
{
    return 0;
}

template <bool MinimizeValue, bool MinimizeArg, typename T>
pair<long long, T> fibonacci_search(long long x_low, long long x_high, function<T(long long)> f)
{
    assert(x_low <= x_high);
    long long offset = x_low - 1;

    T INF = MinimizeValue ? numeric_limits<T>::max() : numeric_limits<T>::lowest();
    auto comp = [](T a, T b) -> bool
    {
        if (MinimizeArg)
            return MinimizeValue ? a > b : a < b;
        else
            return MinimizeValue ? a >= b : a <= b;
    };

    vector<long long> fib = {1, 1};
    while (fib.back() <= x_high - offset)
    {
        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }

    unordered_map<long long, T> fx_cache;
    auto eval = [&](long long idx) -> T
    {
        long long x = idx + offset;
        if (x_low <= x && x <= x_high)
        {
            if (!fx_cache.contains(x))
            {
                fx_cache[x] = f(x);
            }
            return fx_cache[x];
        }

        return INF;
    };

    long long l_idx = 0, r_idx = fib.back();
    while (2 <= fib.size())
    {
        long long step_len = fib[fib.size() - 2];

        long long mid_l_idx = r_idx - step_len, mid_r_idx = l_idx + step_len;

        T fl = eval(mid_l_idx), fr = eval(mid_r_idx);

        if (comp(fl, fr))
        {
            l_idx = mid_l_idx;
        }
        else
        {
            r_idx = mid_r_idx;
        }

        fib.pop_back();
    }

    return MinimizeArg ? pair<long long, T>{r_idx + offset, eval(r_idx)}
                       : pair<long long, T>{l_idx + offset, eval(l_idx)};
}

int main()
{
    long long B, N;
    cin >> B >> N;
    vector<long long> C(N);
    rep(i, N)
    {
        cin >> C[i];
        B += C[i];
    }

    auto f = [&](long long x) -> long long
    {
        long long sum = 0;
        rep(i, N)
        {
            sum += abs(C[i] - x);
        }

        return sum;
    };

    auto [x, fx] = fibonacci_search<true, true, long long>(0, B / N, f);
    cout << fx << endl;

    return 0;
};
0