公式

B - 売上分析 / Sales Analysis 解説 by MMNMM


\(T _ i\) の累積和 \(\displaystyle S _ i=\sum _ {j=1} ^ {i-1}T _ j\ (0\le i\le N)\) によって、\(T _ l+T _ {l+1}+\cdots+T _ {l+K-1}=S _ {l+K}-S _ l\) と表すことができます。 よって、累積和を計算しておくことで、\(M _ l\) の値を \(l\) ごとに定数時間で求めることができます。 あとは、これらの最大値を求め、\(\displaystyle\Bigl\lfloor1000\max _ lM _ l\Bigr\rfloor\) を計算すればよいです。

\(M _ l\) の値の比較や \(\lfloor 1000M\rfloor\) の計算においては、\(M _ l\) ではなく \(KM _ l=S _ {l+K}-S _ l\) の値を管理する形で実装を行うのが楽だと思います。

実装例は以下のようになります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    vector<long> T(N);
    for (long& t : T) {
        cin >> t;
    }

    // 累積和を求める
    for (int i = 1; i < N; ++i) {
        T[i] += T[i - 1];
    }
    T.emplace(begin(T)); // 先頭に 0 を入れておく

    long ans = 0;
    for (int i = 0; i + K <= N; ++i) {
        ans = max(ans, T[i + K] - T[i]); // K 日分の合計の最大値を求める
    }

    cout << ans * 1000 / K << endl; // 1000 倍して K で割って切り捨て
    return 0;
}
N, K = map(int, input().split())
T = [0] + list(map(int, input().split()))

# 累積和を求める
for i in range(1, N + 1):
    T[i] += T[i - 1]

ans = 0
for begin, end in zip(T, T[K:]):
    ans = max(ans, end - begin) # K 日分の合計の最大値を求める

print(ans * 1000 // K) # 1000 倍して K で割って切り捨て

投稿日時:
最終更新: