Python3で解く AtCoder Beginner Contest 185 D - Stamp

結構単純な、数え上げするだけ。問題を把握するのに、少しだけ苦戦したがよく読んだらDにしては結構単純だった。

概要

問題概要は省略。

解くときに考えた内容

最初と最後を同等に考えられる様に $0$ と $n+1$ をリスト $a$ に加える。
（元のリスト $a$ のうち、最初と最後の値を同等に扱える必要にするため結構キモ）
更にソートする。
- 具体的に言うと入力例１だと $[1, 3]$ → $[0, 1, 3, 5]$
0以上の差分のリストを作成する（間にいくつ数値があるかという意味で）
- $[0, 1, 3, 5]$ → $[1, 1]$
この時点で、0以上の差分のリストに値がなければ、白がないということ。
は0以上の差分のリストの最小値になる。
- そうでないと、どう取ってもかならず白を含んでしまうため
差分のリストに含まれる値をで割って、切り上げた値を足し上げていく。
- 切り上げのイメージはX：白、O：青、△：赤として、XOOOOOXを例えばで $k=2$ で△で埋めていくことを考えると割り切れる範囲はX△△△△OXのようなイメージで割り切れない部分は１度重なるようにしてX△△△△△Xとする必要があるから、切り上げするイメージ。

コード

n, m = map(int, input().split())
a = [int(x) for x in input().split()]
# 最初と最後を同等に考えられる様に
# 0とn+1をリストに加える
a.append(0)
a.append(n+1)
# print(a)
num = len(a)
a_s = sorted(a)
l = list()
for i in range(num-1):
    c = (a_s[i+1] - a_s[i] - 1)
    # print(c)
    if c > 0:
        l.append(c)
# print(l)
if len(l) == 0:
    print(0)
else:
    k = min(l)
    cnt = 0
    for i in l:
        # 切り上げ
        if i % k == 0:
            cnt += i // k
        else:
            cnt += i // k + 1
    print(cnt)

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。