概要
- $[1,2,..,N]$を並び替えた数列$a$がある。(例えば$[3,2,4,1]$)
- あるkが与えており、あなたは任意の連続したk個の数値をその区間の最小値で置き換える。
- この数列すべてが最小の値となるのに、何回置き換えが必要か？その最小数を述べよ。
アプローチ
まず、最小の値とは題意から1であることは分かる。つまり、1を区間kずつ伝搬させていくイメージになる。例えば、以下に$N=7, k=3$の例を示す。
一番上を例にとると、図のように1を伝搬させられ、4回ですべての要素が1となる。しかし、これは最小の階数ではない。例えば、中段のように取ることで3回で目的を達成できる。
これをよく見ると、以下のことがわかる。
- なるべく重ね合わせがないようにする(すでに1にした場所を1にしても意味がない
- 順番を入れ替えて考えても問題はない(中段と下段を比較)
このため、以下のように考える、
- 左端からすべてのマスを1マスは重ねて舐める。基本的に重ねるのでk-1マスずつ塗れる
- ただし、最初の塗りは左端を重ねる必要がないので、kマス塗れる
コード
import math
n, k = map(int,input().split())
dat = list(map(int, input().split()))
i = dat.index(1) + 1 # 1 origin で i 個目に 1 がある
reached = k # 最初の1歩はkマス塗れる
# a: 残りはk-1マス塗れるので、残っている分を塗る(k<nなのでマイナスは考えない)
a = math.ceil((n - reached) / (k - 1))
print(1 + a)