外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

H - Too Heavy Sequence

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 350 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

操作 1 回で長さが 1 減るので、操作回数はちょうど N−MN-M 回です。

最後の数列を 11 が MM 個の数列にします。(k=1k = 1 のペアは操作されないのでこれ以上操作が行われることがありません。)

ここから逆向きに、要素 kk を k+1, k+1k+1,\ k+1 に置き換える操作を N−MN-M 回くりかえします。ここでは便宜上いつも先頭の要素に行うことで実装が楽になります。

先頭だけに行うと、値が 22 以上の等しいペアは常に先頭だけになります。なので順方向の操作も毎回先頭で行われ、構築の逆をそのままたどります。

11 が MM 個の数列から構築した場合、最大値は N−M+1N-M+1 なので 10910^9 以下です。

スタックや両端キューをつかって実装できます。

解法例

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)
    
    
    


ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。