$T$ が関係ないやんけ！

問題へのリンク

問題概要

高橋君は街 $1, 2, 3, \dots, N$ の順に訪れる。街 $i$ ではりんごの価値は $A_{i}$ 円である。

高橋君は街 $i$ で $A_{i}$ 円でりんごを好きな数だけ買うことができて、 $j \lt i$ を満たす街 $j$ でそのりんごを好きな数だけ $A_{j}$ 円で売ることができる。ただし、高橋君はりんごを買う操作を合計 $T$ 回しか行うことができない。

高橋君がベストを尽くしたときに得られる金額を $M$ 円とする。

青木君は各街のりんごの価値を下げることができる。高橋君がベストを尽くしたときに得られる金額が $M$ より小さくなるように下げるとき、下げ幅の総和の最小値を求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le A_{i} \le 10^{9}$
$2 \le N \le 10^{9}$
$A$ の値はすべて互いに相異なる
青木君が高橋君の得る金額を減らすことが可能であることが保証される

考えたこと

まずは、「青木君が何もしない状態で高橋君が得られる金額」を考察しよう。少し考えると

$A_{j} - A_{i}$ が最大となるような $(i, j)$ （ $i \lt j$ ）

を考えて、 $T$ 個のりんごすべてについて「街 $i$ で買って街 $j$ で売る」のが最適解を導くとわかる。

ただし注意したいことは、「 $A_{j} - A_{i}$ が最大となるような組 $(i, j)$ 」が複数通りある場合は、 $T$ 個の各りんごについて、そのどの組を選んでもよい。

青木君の戦略

上記を踏まえて、青木君の戦略は、「 $A_{j} - A_{i}$ が最大となるような組 $(i, j)$ 」に対して $A_{j}$ の値を 1 下げることだとわかる。

ただし、そのような組 $(i, j)$ が複数考えられる場合もある。その場合は、そのすべての組についての $A_{j}$ の値を 1 下げれば良い。制約から、 $A$ の値が互いに異なることが保証されているので、1 つの $j$ に複数の $i$ が対応したり、1 つの $i$ に複数の $j$ が対応したりするような可能性はない。

実装上は計算量に気を遣う必要がある。ここでは、後ろから次の 3 つの値を管理することにした。

max_val：ここまでの値の最大値
max_diff：ここまでの範囲内での 2 値の差の最大値
res：ここまでの範囲内で、最大差を達成する 2 値が何組あったか

これによって、計算量は $O(N)$ となった。

コード

#include <bits/stdc++.h>
using namespace std;
template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }

int main() {
    long long N, T;
    cin >> N >> T;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    long long res = 0, max_val = 0, max_diff = 0;
    for (int i = N - 1; i >= 0; i--) {
        if (chmax(max_diff, max_val - A[i])) res = 1;
        else if (max_diff == max_val - A[i]) res++;
        chmax(max_val, A[i]);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 047 D - 高橋君と見えざる手 (ARC 063 D) (1Q, 水色, 400 点)

問題概要

制約

考えたこと

青木君の戦略

コード