[AtCoder] ABC 185 D - Stamp

連続する白マスの列を数え上げて、その白マスの個数 $w_i$ の列を $W$ とします。
その $W$ の中で最短の列の長さを $k$ として、 $W$ のそれぞれ $w_i$ に対して $\lceil \frac{w_i}{k} \rceil$ で塗り上げれば最小回数になります。

$\sum \lceil \frac{w_i}{k} \rceil$

言語はC++(GCC 9.2.1)でAtCoderのコードテストで確認しています。

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

int main() {
  int N, M, B;
  cin >> N >> M;
  vector<bool> A(N, false);
  for (int i = 0; i < M; i++) {
    cin >> B;
    A[B-1] = true;
  }

  vector<int> White;
  int start = 0;
  bool isWhite = false;
  for (int i = 0; i < N; i++) {
    if (A[i] && isWhite) {
      White.push_back(i - start);
      isWhite = false;
    } else if (!A[i] && !isWhite) {
      start = i;
      isWhite = true;
    }
  }
  if (isWhite) {
    White.push_back(N - start);
  }

  if (!White.size()) {
    cout << 0 << endl;
    return 0;
  }

  sort(White.begin(), White.end(), greater<int>{});

  int K = White.back(), ans = 0, len = White.size();

  for (int i = 0; i < len; i++) {
    ans += White[i] % K ? White[i] / K + 1 : White[i] / K;
  }

  cout << ans << endl;
}