解説
操作 1 回で長さが 1 減るので、操作回数はちょうど 回です。
最後の数列を が 個の数列にします。( のペアは操作されないのでこれ以上操作が行われることがありません。)
ここから逆向きに、要素 を に置き換える操作を 回くりかえします。ここでは便宜上いつも先頭の要素に行うことで実装が楽になります。
先頭だけに行うと、値が 以上の等しいペアは常に先頭だけになります。なので順方向の操作も毎回先頭で行われ、構築の逆をそのままたどります。
が 個の数列から構築した場合、最大値は なので 以下です。
スタックや両端キューをつかって実装できます。
解法例
from collections import deque
N, M = map(int,input().split())
A = deque([(1, M)])
for i in range(N-M):
k, v = A.popleft()
A.appendleft((k, v-1))
A.appendleft((k+1, 2))
sum_ = 0
res = []
for k, v in A:
sum_ += v
for _ in range(v):
res.append(k)
print(*res)
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。