Codeforces Round 887 (Div. 1)

　Bまで二完。Aがすぐ分からなかったが、Bを解いた後戻って考えたら分かった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 887 (Div. 1) pretestはBまで。
A 後ろから見る。その数字が何番目から来たかは二分探索で分かる。二分探索二回してlog二つついてるのが怖い
B sortすると、どこから負にしてどこから正にしたら良いか分かるので、そこから左右に埋めて行く。

— titia (@titia_til) July 23, 2023

C. Ina of the Mountain

　解説AC。解法ツイートでpriority queueを使うなどと言われても分からなかったが、公式Editorialが丁寧だった。

　（A[i]=kのものはA[i]=0に前処理した上で、）

・A[i]かA[i]+kのどちらかを使うと思って良い。

・登りのときだけコストがかかると考える。そうすると、次の戦略が最適：下りはとりあえず下っておくとする。下りを後で登りに変更することを考えると、-xの下りを登りに変更した場合、k-xのコストがかかることが分かる。なので、登るとき、「今までの下りのうちのどれかを登りに変更するか、ここを登るか」これらのうちの最小値を選べばよい。（ここでpriority queueを使う）