[AtCoder] ABC 185 D – Stamp
問題
方針
数列 \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません