Educational Codeforces Round 120 (Rated for Div. 2)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 120 (Rated for Div. 2) Eが分からず終了。
B 0と1で場合分けしてそれぞれをソート。
C 最初、min(A)をいくつまで減らすか三分探索かと思いハマった。何個そのままにするか？　で全探索。
D 「最初に動かす1はどれか？」で場合分け

— titia (@titia_til) December 27, 2021

E. Math Test

　解説AC。

　abs(x) = max(x, -x)で変形するという典型だが、この式を使おうという発想が全く出なかったのはまずい。これにより、N人を、予想より高い点を取ったか、低い点を取ったか、で分けてbit 全探索する。

　PyPyだとTLEにも悩まされた。

　bit 全探索して、実際にきちんとスコアを求めているとTLEしてしまう。そうではなくて、プラス側に割り振った場合 x - r点を、マイナス側に割り振った場合 r - x点を取ったとして計算してしまっても最大値は変わらない（xを実際の点、rを予想の点としています）。それを利用すると定数倍改善されてACできる。

　今回は定数倍の改善に過ぎないけど、これを利用して計算量を改善することもあると思うので、後半のテクニックも頭に入れておきたい。