CF Round #642 E - K-periodic Garland


Tags:cpcodeforcesdiv3greedydp

問題

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

問題文

nn 個のランプがあり、 sis_i0 ならランプ ii は消灯、 1 ならランプ ii は点灯している。
整数 kk も与えられる。

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

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

kk-periodic にするために必要な操作の回数の最小値は?

制約

  • 1t2.5×1041 \le t \le 2.5 \times 10^4
  • 1n1061 \le n \le 10^6
  • 1kn1 \le k \le n
  • nn の総和は 10610^6 を超えない

サンプル

6
9 2
010001010
9 3
111100000
7 4
1111111
10 3
1001110101
1 1
1
1 1
0
1
2
5
4
0
0

考察

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