けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 185 D - Stamp (茶色, 400 点)

番兵を入れるとかすれば、怖いケースをあらかじめ除去できそう

問題概要

左右方向一列に  N 個のマスが並んでいます。

この  N 個のマスのうち、マス  A_{1}, \dots, A_{M} M 個のマスは青色で、それ以外のマスは白色です。

あなたは一回だけ、正整数  K を一つ選んで幅  K のハンコを作ります。幅  K のハンコを一回使用すると、 N 個のマスのうち連続する  k マスを選び、それらを赤色に塗り替えることができます。ただしその際、その  K 個のマスの中に青色のマスが入っていてはなりません。

 K とハンコの使用方法をうまく決めた時、最小で何回ハンコを使用すれば、白色のマスが存在しない状態にすることができるでしょうか。

制約

  •  1 \le N \le 10^{9}
  •  0 \le M \le 2 \times 10^{5}

考えたこと

下図のように、

  • 白いところの塊に分けて
  • その長さの最小値を  K とする (これより長いと青マスに被ってしまう)

というふうにして、

  • 白マスにスタンプを押していく

とすれば OK。

f:id:drken1215:20201214011725p:plain

実装するときには、さらに下図のように、両端に青いマスを追加して考えるとわかりやすくなる。こういうのを「番兵」といったりする。

f:id:drken1215:20201214011851p:plain

あと、青いマスが連続しているところを「長さ 0 の白塊」として処理しないように注意!!! 「長さ 0 の白塊」は除外して考えないといけない!!!

コーナーケース

以下のケースがちょっと怖い

  • 全部が「青」
  • 「青」が 1 個もない

実装次第だけど、これらは気にしなくてもいいようにできる。下の実装では、全部が「青」という場合は、ベクトル v が空になるだけで答えは結局 0 になる。

「青」が 1 個もないというケースは、番兵さえ入れておけば関係ない。

コード

計算量は  A を小さい順に並び替える必要性から、 O(N \log N) となる。

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

int main() {
    long long N, M;
    cin >> N >> M;
    vector<long long> A(M);
    for (int i = 0; i < M; ++i) cin >> A[i];
    sort(A.begin(), A.end());

    // 番兵追加
    A.insert(A.begin(), 0);
    A.push_back(N+1);

    // 白塊に分解 (同時に最小値も求める)
    vector<long long> v;
    long long K = N;
    for (int i = 0; i+1 < A.size(); ++i) {
        long long len = A[i+1] - A[i] - 1;
        if (len > 0) {
            v.push_back(len);
            K = min(K, len);
        }
    }

    long long res = 0;
    for (auto len : v) res += (len + K - 1) / K;
    cout << res << endl;
}