ARC063 - D - 絶滅

D - 高橋君と見えざる手 / An Invisible Hand

ぱっと見 600 くらいに見えたけどよく見たら 400 だった．

高橋くんの最適戦略は i < j のもとで A[j] - A[i] が最大となる (i, j) のペアを見つけてきて
i で買って j で売ればいい．

青木くんはそのような (i, j) のペア(複数存在するなら全て)に対して
A[j] の値を decrement すれば高橋くんの利益を 1 下げることができる．

ここまではすぐ分かったけど肝心のアルゴリズムが O(N²) 以外思いつかなかった．
仕方なく解説を見ると O(NlogN) どころか O(N) だったので目玉ひん剥いた．

最小値を保持して差分を計算するテクニックは
めちゃくちゃ重要そうなのでこれを機に脳に焼き付けておこう…

int main() {

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

    ll N, T;
    cin >> N >> T;

    vector<ll> A(N);
    cin >> A;

    map<ll, ll> B;
    ll minA = INT64_MAX;
    for (int i = 0; i < N; i++) {
        minA = min(minA, A[i]);
        B[A[i] - minA]++;
    }

    cout << (*(--B.end())).second << endl;

    return 0;
}

Submission #2623548 - AtCoder Regular Contest 063