arc086_b

構築する

最短である必要はない

2N回も必要なケースあるのかな？

6,5,4,3,2,1を全部+1だけで条件を満たそうとすると超えるが、そんなことはしない

2番目に対して1番目以上になる最小の数を足し…とやっていってOKか？

O(NlogN)

Nが50とかなり小さい

もっとオーダーの大きなアルゴリズム？

公式解説

元の数ではなく更新した数が使われるのが厄介だと思ったが、むしろそれを活用する

符号が揃っている場合は累積和でできる

気づかなかったなぁ