[AtCoder] ABC 185 D – Stamp

2020年12月13日

問題

方針

数列 \( A_i \) の順序を変えても影響はないので、\( A_i \) を昇順に並び替えて考えます。\( k \) の最大値は、各マスの差の最小値なので、

\[ k = \min_{1 \leq i \leq M – 1} (A_{i + 1} – A_{i}) \ (A_{i + 1} – A_{i} \neq 0 )\]

となりますが、\( A_{1} \neq 1 \) または \( A_{M} \neq N \) のときも考慮する必要があるので、

• \( A_1 \neq 1 \) のとき

\[ k \leftarrow \min(k, A_{0})\]

• \( A_M \neq N \) のとき

\[ k \leftarrow \min(k, N – A_{M})\]

と更新します。

したがって、ハンコの使用回数を \( x \) とすると、

\[ x = \sum_{i = 1}^{M – 1} \left \lfloor \dfrac{A_{i + 1} – A_{i} – 1 + k – 1}{k}\right \rfloor \]

となりますが、\( A_{1} \neq 1 \) または \( A_{M} \neq N \) のときも考慮して、

• \( A_1 \neq 1 \) のとき

\[ x \leftarrow x + \left \lfloor \dfrac{A_1 – 1 + k – 1}{k}\right \rfloor\]

• \( A_M \neq N \) のとき

\[ x \leftarrow x + \left \lfloor \dfrac{N – A_M + k – 1}{k}\right \rfloor\]

となります。

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    if (M == 0) {
        cout << 1 << "\n";
        return 0;
    }
    int A[M];
    for (int i = 0; i < M; i++) {
        cin >> A[i];
    }
    sort(A, A + M);
    int k = N;
    for (int i = 0; i < M - 1; i++) {
        if (A[i + 1] - A[i] == 1) continue;
        k = min(k, A[i + 1] - A[i] - 1);
    }
    if (A[0] != 1) {
        k = min(k, A[0] - 1);
    }
    if (A[M - 1] != N) {
        k = min(k, N - A[M - 1]);
    }
    ll sum = 0;
    for (int i = 0; i < M - 1; i++) {
        sum += (A[i + 1] - A[i] - 1 + k - 1) / k;
    }
    if (A[0] != 1) {
        sum += (A[0] - 1 + k - 1) / k;
    }
    if (A[M - 1] != N) {
        sum += (N - A[M - 1] + k - 1) / k;
    }
    cout << sum << "\n";
    return 0;
}