Codeforces Round 973 (Div. 2)

　Cまで三完。

コンテストへのリンク

D. Minimize the Difference

　解説AC。

　問題文で与えられた操作を用いて、広義単調増加にすれば良い（逆に、A[i]<=A[i+1]となったらそれ以上操作はしない）だろうことにはコンテスト中に気付いていた。

　どういう操作でそれを実装できるかが分からなかった。

　これは、[値, その要素の個数]を持って、配列の値を見たら後ろの要素とマージしていく……とすれば実装できる。

　マージすることは思いつくけど、ランレングス圧縮のようなことをすると計算量が減るとは気付かなかった。

　この方法を思い付けなかったのは悔しい。

E. Prefix GCD

　自力AC。

　直感的に正しそうな貪欲を実装したらそのままACだった。証明も、こんな感じかな？　と思ったもの（ちゃんと証明はしていない）で良さそうだった。