Codeforces Round #642 (Div. 3) E. K-periodic Garland

問題へのリンク

問題概要

とのみで構成された文字列が与えられる。隣り合うの距離をちょうどにするために必要な操作回数の最小値を求めよ。

解説

周期で考える。

• ある一つので割った余りが等しいindexについて、

という形に、

• 他のindexについては

すべて

になっていればよいことがわかる。これは、耳DPで前から状態を管理すると実現できる。

提出

提出へのリンク

void solve(){
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    int cnt1 = 0;
    vvec<int> V(K);
    rep(i,N){
        V[i%K].push_back(S[i]-'0');
        cnt1 += S[i] - '0';
    }
    ll ans = INFLL;
    //i番目の分割
    rep(i,K){
        //00...111...000にする最小値 耳DP
        int M = V[i].size();
        vvec<ll> dp(M+1, vec<ll>(3,INFLL));
        dp[0][0] = dp[0][1] = dp[0][2] = 0;
        int tmp = 0;//この区間に含まれる1の数
        rep(j,M){
            tmp += V[i][j];
            //from 0
            {
                //to 0
                chmin(dp[j+1][0], dp[j][0] + V[i][j]);
                //to 1
                chmin(dp[j+1][1], dp[j][0] + (V[i][j]^1));
            }
            //from 1
            {
                // to 1
                chmin(dp[j+1][1], dp[j][1] + (V[i][j]^1));
                // to 2
                chmin(dp[j+1][2], dp[j][1] + V[i][j]);
            }
            //from 2
            {
                // to 2
                chmin(dp[j+1][2], dp[j][2] + V[i][j]);
            }
        }
        ll minn = min({dp[M][0],dp[M][1], dp[M][2]});
        chmin(ans, minn + cnt1 - tmp);
    }
    cout << ans << endl;
}