CF Round #642 E - K-periodic Garland - Competitive Programming Library

問題

https://codeforces.com/contest/1353/submission/127026730

問題文

$n$ 個のランプがあり、 $s_i$ が 0 ならランプ $i$ は消灯、 1 ならランプ $i$ は点灯している。
整数 $k$ も与えられる。

1 回の操作で、1 つのランプを選んで、状態を反転させることができる。

$k$ -periodic とは、それぞれ ON の状態のランプがちょうど $k$ 個離れているような状態のことである。例えば、100100100 は $3$ -periodic である。

$k$ -periodic にするために必要な操作の回数の最小値は？

制約

$1 \le t \le 2.5 \times 10^4$
$1 \le n \le 10^6$
$1 \le k \le n$
$n$ の総和は $10^6$ を超えない

サンプル

考察

DP した。
具体的には、「dp[i] = $i$ 番目が ON のとき、それより前のランプを最小でいくつ変える必要があるか」をまず考える。
その後 $i$ 番目が一番左にある場合とそうでない場合で最小値をとる。
全部調べたら、 $i$ 番目が一番右にあることを考えて、加える。
最終的には「dp[i] = $i$ 番目が ON で一番右にあるときに最小でいくつ変える必要があるか」になってる。
これの最小値を出力する。

毎回「いくつ変えるべきか？」を数えると間に合わないので、累積和を使う。

また、コーナーケースで全部 OFF の場合があるので注意。

コード

https://codeforces.com/contest/1353/submission/127026730

void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vector<int> sum(n + 1, 0);
  rep(i, n) {
    sum[i + 1] = sum[i] + (s[i] - '0');
  }
  vector<int> dp(n, 1e9);
  dp[0] = 0;
  rep(i, n) {
    int f = sum[i] - (s[i] - '1');
    int g = 1e9;
    if (i - k >= 0) {
      g = dp[i - k] + (sum[i] - sum[i - k + 1]) - (s[i] - '1');
    }
    dp[i] = min(f, g);
  }
  rep(i, n) {
    dp[i] = dp[i] + sum[n] - sum[i + 1];
  }
  dp.push_back(sum[n] - sum[0]);
  cout << *min_element(dp.begin(), dp.end()) << endl;
}