AtCoder Beginner Contest 185 D問題

AtCoder Python

前書き

atcoder.jp

D問題

難易度：茶色
時間：45分

おおよそのアルゴリズムは10分ほどで浮かび、実装していましたが、
場合分けを忘れておりWAを出してしまい、時間ロス。

「白色タイルを無くすためにスタンプを押そう！でも青色タイルには押さないでね」という問題。
スタンプのサイズは最初の一回のみ決定できます。
白色タイルは1≤N≤10**9、青色タイルは1≤M≤2*10**5です。

1. まず最初にすべき場合分け処理

  • 青色のタイルが全く存在しない場合はサイズNのスタンプで1度押すだけ
  • 青色のタイルがNの場合は白色タイルが存在しないので0度

2. 連続する白色タイルの最小値(>0)を求めます

  • 次に青色タイルが0個目、N+1個目に存在すると仮定→両端処理
  • 白色タイルの連続値を取得、同時に連続値の最小値（→スタンプのサイズ）も取得

3. 白色タイルにスタンプを押す最小回数を求めます

import math
import sys
N, M = map(int, input().split())
Delta,count,size = [],0,N
A = [aa for aa in map(int, input().split())]
A.sort()

if M==0: 
  print(1)
  sys.exit()
if len(A)==N:
  print(0)
  sys.exit()

A.insert(0,0)
A.append(N+1)
for i in range(0,M+1):
  c=A[i+1]-A[i]
  Delta.append(abs(c-1)) 
  if c-1>0: size = min(size, c-1)

for j in Delta:
  count += math.ceil(j/size)
print(count)

ACでした。