Edit

【pythonでABC185を解説】D - Stamp

問題概要

問題ページ

D - Stamp
D - Stamp

問題ページへ移動する

問題文

左右方向一列に \(N\) 個のマスが並んでいます。左から \(i\) 番目のマスをマス \(i\) と呼ぶことにします。
この \(N\) 個のマスのうち、マス \(A_1\), マス \(A_2\), マス \(A_3\), \(\dots\), マス \(A_M\) の \(M\) 個のマスは青色で、それ以外のマスは白色です。(\(M = 0\) の可能性もあり、その場合青色のマスはありません。)
あなたは一回だけ、正整数 \(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\) は互いに異なる
  • 入力は全て整数

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    if m == 0:
        print(1)
    else:
        a = sorted(list(map(int, input().rstrip('\n').split())))
        if a[0] != 1:
            a = [0] + a
        if a[-1] != n:
            a += [n + 1]
        dif = []
        mn = 10 ** 20
        for i in range(1, len(a)):
            dif_v = a[i] - a[i - 1] - 1
            if dif_v != 0:
                mn = min(mn, dif_v)
                dif.append(dif_v)
        if mn == 10 ** 20:
            print(0)
        else:
            total = 0
            for v in dif:
                total += (v + mn - 1) // mn
            print(total)


if __name__ == '__main__':
    solve()

-Edit
-