ABC185 D問題 Stampを解く

ABC185 D問題 Stampを解説します。

atcoder.jp

問題の内容

左右一列にN個のマスが並んでいます。そのうちM個のマスが青色でそれ以外は白です。
1回だけ幅がkのスタンプを作成して、赤色で白いマスを塗っていくときに、全部の白いマスを赤くするには最小で何回スタンプを使えば良いか求める問題です。

解く方針

まず制約を見て、ループできるのはMくらいだなと目星をつけます。
連続した白いマスからスタンプの幅を求めて、それぞれの連続した白いマスについて何回スタンプを使えば良いか集計して答えを求めます。

具体的な解き方

青色のマスの位置を区切りとして見て、連続した白いマスの数を格納する配列を作成します。

for i in range(M):
    if i == 0:
        blanks.append(a_arr[i] - 1)
        continue
    blanks.append(a_arr[i] - a_arr[i - 1] - 1)
blanks.append(N - a_arr[-1])

次にスタンプの幅を決めるために幅kを求めます。
幅kは最大でも連続した白いマスの最小値になります。
連続した白いマスの最小値が2のときに、それより大きい幅のスタンプを押すと青色のマスを塗ってしまうことになります。

# 最小値を求めるので、ありえないくらい大きい数を初期値にします
minimum = N
for b in blanks:
    # bが0の時は青色のマスが連続しているのでスキップ
    if b == 0:
        continue
    minimum = min(minimum, b)

幅kが求まったら、連続した白いマスの数をkで割ります。割り切れない場合は切り上げにします。
例えば、kが3で、白いマスが5個連続していたら、2回で白いマスを塗りつぶせます。
その数を合計したのが答えになります。

ans = 0
for b in blanks:
    ans += ceil(b / minimum)
print(ans)

全体のコードは以下のようになります。

from math import ceil
N, M = map(int, input().split())
# Mが0の時の答えは1
if M == 0:
    print(1)
    exit()
a_arr = list(map(int, input().split()))
# 探索しやすいように青いマスの位置はソートしておく
a_arr.sort()
# インデックス0は参照しないので、適当な値で埋めておく
blanks = [0]
# 連続した白いマスの数を格納する配列を作る
for i in range(M):
    if i == 0:
        blanks.append(a_arr[i] - 1)
        continue
    blanks.append(a_arr[i] - a_arr[i - 1] - 1)
# 一番後ろの青いマスの位置と一番後ろの位置から一番最後の連続した白いマスを求める
blanks.append(N - a_arr[-1])
# 最小値を求めるので、ありえないくらい大きい数を初期値にします
minimum = N
for b in blanks:
    # bが0の時は青色のマスが連続しているのでスキップ
    if b == 0:
        continue
    minimum = min(minimum, b)

ans = 0
for b in blanks:
    ans += ceil(b / minimum)
print(ans)

基本的には問題の通りに書けば良いのでD問題としては易しめでした。