ABC101 C - Minimization
備忘録
問題
回答
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array import numpy as np # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # from collections import defaultdict, deque sys.setrecursionlimit(10000000) ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, K = il() A = il() ret = 1 N -= K while not N <= 0: N -= K - 1 ret += 1 print(ret) if __name__ == '__main__': main()
考え方
数列を選んだ要素の中で最小値に置き換え続けるとき、
最終的には全ての要素が1
になる。
そのため、一番最初に行う置き換えの操作は、
1
を含むK
個の要素を1
に置き換える操作が必要になる。
そのため、N
個の要素のうち、K
個の要素を最小の値に置き換えたとき、
残りはN - K
個の要素を置き換える操作が必要になる。
あとは残りのN - K
個の要素を置き換える操作が何回必要か求める。
K
個の要素の中のうち、最も小さい数(1
)以外のK - 1
個が1度の操作で置き換え可能な最大数となる。
つまり、1度の操作で置き換えることが可能な要素の数はK - 1
個が最大となる。
1度に置き換えることが可能な要素数が判明したら、
あとはN
個の要素から何回置き換える操作(N -= K - 1
)が出来るかを求めれば回答を得られる。