AtCoder-ABC185 D - Stamp【Pythonの解答例】 - ebisukeプログラミング初心者脱出黙示録

今回はAtCoder Beginner Contest185 D問題についての記事です。
コンテストでも解けず、解説をみてもよくわからず…
結局こちらのサイトで勉強させていただきました。
zenn.dev
解答例がこの記事にありますが、m193hさんのコードと同じ（変数名を変えたくらい）ですので、リンク先でご覧になったほうがよいです。
モノマネでも私の中では勉強してきた一部ですので記事にしましたが、ただのコピーですのでぜひオリジナルをご覧ください。

AtCoder Beginner Contest185 D - Stamp

D - Stamp

問題文

左右方向一列に N個のマスが並んでいます。左からi番目のマスをマスiと呼ぶことにします。
このN個のマスのうち、マス $A_{1}$ , マス $A_{2}$ , マス $A_{3}$ ,…, マス $A_{M}$ のM個のマスは青色で、それ以外のマスは白色です。(M=0の可能性もあり、その場合青色のマスはありません。)
あなたは一回だけ、正整数kを一つ選んで幅kのハンコを作ります。幅kのハンコを一回使用すると、N個のマスのうち連続するkマスを選び、それらを赤色に塗り替えることができます。ただしその際、そのk個のマスの中に青色のマスが入っていてはなりません。kとハンコの使用方法をうまく決めた時、最小で何回ハンコを使用すれば、白色のマスが存在しない状態にすることができるでしょうか。

制約

・1≤N≤ $10^{9}$
・0≤M≤2× $10^{5}$
・1≤ $A_{i}$ ≤N
・ $A_{i}$ は互いに異なる
・入力は全て整数

解答例

n, m = map(int,input().strip().split())
a_list = list(map(int, input().strip().split()))
a_list = [0] + a_list + [n + 1]
m += 2

a_list.sort()
stamp_len = 10 ** 10
white_space = []
for i in range(1,m):
    count = a_list[i] - a_list[i - 1] - 1
    if count <= 0:
        continue
    stamp_len = min(stamp_len,count)
    white_space.append(count)

ans = 0
for i in white_space:
    ans += (i + stamp_len -1) // stamp_len

print(ans)

解説

m193hさんの解説を参照されたほうがよいですが、一応…
青マスの隙間にある白マスが何個連続するかを確認し、連続する白マスの最小数をスタンプの幅とします。
幅がきまれば白マスを埋めるためには何回スタンプを押すか求めていきます。
数字を割ったとき切り上げの仕方がありますので、次はそれを記事にしようかと思います。

今回もまた周りの方に勉強させてもらいました。
先は長いでしょうが周りの方から勉強させていただきながら地道に進んでいきたいです。

以前のABC185の記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com