Yukicoder078 クジ付きアイスバー

問題概要

A君は当たりクジ付きのアイスバーが大好きである。
アイスバーには「ハズレ」と「1本当たり」と「2本当たり」がある。
ハズレは何ももらえないが、当たりだとその本数をタダでもらえる。

お店ではアイスバーが箱詰めされて売られている。
1つの箱には$N$本のアイスバーが入っている。
A君は箱の先頭から順にしかアイスバーを取り出すことはできない。
買う場合も当たりと引き換えの場合もこの箱からアイスバーを取り出す。
1つの箱の中のハズレと当たりクジの配置はどの箱も同じである。
お店には1つのアイスバーの箱があり、売り切れると1つの新しい箱を補充する。
いまお店には新しい手つかずのアイスバーの箱がある。
A君は最初は「当たり」クジを持っておらず予算は無限にある。
$K$本のアイスバーを食べるためにはA君は最低何本のアイスを買う必要があるか?

$N\leqq50$、$K\leqq2*10^9$

yukicoder078

解法

区間を次のように分割する。
$[$愚直$][$前回のあたりが影響する区間$]^{*}[K\%N$が真なら前回のあたりが影響する$]$
とすれば良い。

計算量:$O(N)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int N, K; cin >> N >> K;
        string s;  cin >> s;
        int ret = INF;
        int free = 0, cnt = 0;
        FOR(i, 0, N) {
            if (free > 0) {
                free--;
            }
            else {
                cnt++;
            }
    
            free += s[i] - '0';
            if ((i + 1) % N == K%N) {// K個目を買い終える
                ret = min(ret, cnt);
            }
        }
        int ans = ret;
    
        int t = K / N;
        if (t) {
            ans = cnt + (t - 1)*(max(0, cnt - free)) + (K%N ? max(0, ret - free) : 0);
        }
    
        cout << ans << "\n";
    
        return 0;
    }