Codeforces Round 892 (Div. 2)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 892 (Div. 2) Dまで。
A 最大のものをCへ。
B 小さい方二つずつを見て、二つ目の和-二つ目のmin+一つ目のmin
C 後半いくつかを逆順に並べるのを試す
D bが大きい方から見て遅延セグ木でできそう→TLE→長いこと定数倍バトルした後普通のセグ木でできることに気付きAC。

— titia (@titia_til) August 12, 2023

E. Maximum Monogonosity

　解説AC。

　絶対値を外すDPらしいと聞いたのに理解できず、けんちょんさんのブログを見てAC。

　分かってしまえば難しくないのだが……。

　とりあえず、絶対値を外すと聞いたのに絶対値をmaxに変える変形ができなかったのは反省。

　この問題のように、

・|A|=max(A, -A)

　を用いて絶対値を外すだけで道が開ける問題は結構ある（たとえば、この問題を思い出した）。とりあえず絶対値は外して、maxの式にして考えるくらいの気持ちで良いかもしれない。