ARC069 - C

C - Scc Puzzle

問題ページ

O(1) なんだろうけどめんどいし二分探索でえいでしょ

整数を引数に取る凸関数の argmax を二分探索で求めるやつ*1を std::function でテンプレ化した
結構コードがきれいになるのと二分探索が脳死で書けるのでかなり重用している

ll S, c;

// c から S を n 個作った場合に作ることのできる Scc の数
ll func(ll n) {
    ll nS = S + n;
    ll nc = c - 2 * n;
    return min(nS, nc / 2);
}

//[from, to)におけるunimodalFuncのargmax(もし複数ある場合は一番若い番号)を返す
template<typename Ind, typename Val>
Ind Maximize(Ind from, Ind to, function<Val(Ind)> unimordalFunc) {
    // d[i] = a[i] - a[i-1]とする。
    // このとき、d[i] > 0 <=> a[i] > a[i-1]なので、
    // d[i] > 0なる最大のi in (from, to)を見つけると、a[i]が最大値
    for (; to - from > 1;) {
        Ind mid = (from + to) / 2;
        (unimordalFunc(mid) - unimordalFunc(mid - 1) > 0 ? from : to) = mid;
    }
    return from;
}

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> S >> c;

    ll n = Maximize<ll, ll>(0, c / 2, func);

    cout << func(n) << endl;

    return 0;
}

Submission #2528887 - AtCoder Regular Contest 069

*1:この記事のやつ