【AtCoder】ABC 185 D - Stamp

2026-11-07

AtCoder/ABC/D問題 AtCoder/ABC/400点問題 AtCoder/茶Diff AtCoder/NoviSteps/4Q AtCoder/番兵を入れて考える競技プログラミング

D - Stamp

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 490 / NoviSteps: 4Q / 配点: 400 点

問題概要

左右方向一列に $N$ 個のマスが並んでおり、左から $i$ 番目のマスをマス $i$ とする。

この $N$ 個のマスのうち、マス $A_1$ , マス $A_2$ , マス $A_3$ , $\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$
$1 \le A_i \le N$
$A_i$ は互いに異なる
入力は全て整数

考察

白いマスの連続区間の長さを $l_1, l_2, \dots, l_n$ とする。

このとき、ハンコの幅として可能なのは $k \leq \min_{i} l_i$ であり、使用回数を最小化するためには、 $k = \min_{i} l_i$ とするのが最適である。

この $k$ が決まれば、操作回数は $\sum_{i=1}^{n} \lceil \frac{l_i}{k} \rceil$ で求めることができる。

実装時は、左右端に番兵として仮想の青色マスを追加してから $A$ を昇順にソートすれば、 $M = 0, N$ のようなコーナーケースの処理を簡単にすることができる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define all(x) (x).begin(), (x).end()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6. 
7.constexpr auto PI = 3.14159265358979;
8.constexpr int INF = 1e+9;
9. 
10.template <class T1, class T2>
11.inline auto div_ceil(T1 a, T2 b)
12.{
13.    if (b < 0)
14.        a *= -1, b *= -1;
15.    if (a <= 0)
16.        return a / b;
17.    else
18.        return (a - 1) / b + 1;
19.}
20. 
21.template <typename T>
22.inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }
23. 
24.// ======================================== //
25. 
26.int main()
27.{
28.    int N, M;
29.    cin >> N >> M;
30.    vector<int> A(M + 2);
31.    A[0] = 0, A[M + 1] = N + 1;
32.    rep(i, 1, M + 1) cin >> A[i];
33. 
34.    sort(all(A));
35. 
36.    vector<int> v;
37.    int k = INF;
38.    rep(i, 0, M + 1) {
39.        int l = A[i + 1] - A[i] - 1;
40. 
41.        if (l > 0) {
42.            v.push_back(l);
43.            chmin(k, l);
44.        }
45.    }
46. 
47.    int ans = 0;
48.    for (auto x : v) {
49.        ans += div_ceil(x, k);
50.    }
51. 
52.    cout << ans << endl;
53. 
54.    return 0;
55.}