Codeforces Round #687 (Div. 1) A. Bouncing Ball (R1400)

個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。

• 問題へのリンク

問題概要

整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。

• 文字列 中の文字 "0" を "1" に変更する (コスト )
• 先頭の 1 文字を削除する (コスト )

操作によって次の条件を満たすようにするための、最小コストを求めよ。

• がすべて "1"

制約

• (テストケース数)
• 

考えたこと

次のような 飛ばしの累積和を求めれば OK。

• num[ v ] := の 番目以降に "0" が何個あるか

これは次のように求められる。

vector<long long> num(N+1, 0);
for (int i = N-1; i >= 0; --i) {
        int add = (S[i] == '0');
        num[i] = add;
        if (i+K < N) num[i] += num[i+K];
}

これを求めておけば、「先頭の 1 文字を削除する」操作を何回実施するかで場合分すれば OK。計算量は全体で となる。

コード

#include <bits/stdc++.h>
using namespace std;

template<class T> inline bool chmin(T& a, T b) { 
    if (a > b) { a = b; return 1; } 
    return 0; 
}

int N, P, K;
long long X, Y;
string S;

long long solve() {
    cin >> N >> P >> K >> S >> X >> Y;
    vector<long long> num(N+1, 0);
    for (int i = N-1; i >= 0; --i) {
        int add = (S[i] == '0');
        num[i] = add;
        if (i+K < N) num[i] += num[i+K];
    }
    long long res = 1LL<<60;
    for (long long i = P; i <= N; ++i) {
        long long remove = (i-P) * Y;
        long long add = num[i-1] * X;
        chmin(res, remove + add);
   }
    return res;
}

int main() {
    cin.tie(0); 
    ios::sync_with_stdio(false);

    int T;
    cin >> T;
    while (T--) cout << solve() << endl;
}