ABC185 D - Stamp

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    A = il()
    # 青いマスをソートしておく
    A.sort(reverse=True)

    Q = N
    ret = []
    # 左から順に連続する白いマスの数を数える
    for a in A:
        if Q - a != 0:
            ret.append(Q-a)
        Q = a - 1

    # 最も右にしか青いマスが存在していない場合
    if Q != 0:
        ret.append(Q)

    ans = 0
    if len(ret) == 0:
        # 全て青いマスの場合
        print(0)
        exit()
    else:
        # 連続する白いマスのうち最も小さい長さをハンコの幅とする
        i = min(ret)
        for r in ret:
            # ハンコを何度使用するか
            d, m = divmod(r, i)
            ans += d
            if m != 0:
                # 余りが存在する場合には+1
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

考え方

連続する白いマスのうち、連続するマスの最も小さい数が使用できるハンコの幅となります。

仮に入力例１のように、５つマスが並び、1つ目と3つ目が青いマスの場合には、
■□■□□となり、連続する白いマスは□と□□です。
このとき、大きい方で幅２のハンコを使用する場合、
どのようにしても白い1マスに使用することができません。
そのため、連続するマスのうち最も小さい数をハンコの幅にする必要があります。

ハンコの幅が決まれば、あとは連続する白いマスに何回使用するか数えるだけです。
実装は愚直に考えたことを上から並べてます。