競プロ備忘録

競プロerの備忘録

技術室奥プログラミングコンテスト#6 Day1D - ABS SUM

コンテスト名が長すぎる…

解法

取り得る区間の累積和の絶対値の総和を求めよと言われている。

まず配列 Aについて区間 [l, r)の累積和の求め方を考えると、 rまでの累積和から、 l- 1までの累積和を引けば求まる。
つまり、 1から iまでの累積和を SA _ {i}と置けば、

\sum _ {i=l} ^ {r} {A _ {i}} = SA _ {r} - SA _ {l - 1}

となる。

ところで、絶対値を求めよと言われているので、以下のように場合分けする。

\displaystyle |\sum _ {i=l} ^ {r} {A _ {i}}| = \left\{ \begin{array}{ll} SA _ {r} - SA _ {l - 1} & (SA _ {r} \ge SA _ {l - 1}) \\ SA _ {l - 1} - SA _ {r} & else \end{array} \right.


この式をもとに SA _ {i}本位で考えると、

  • i未満のインデックス向けには、自身より大きいものの数だけ SA _ {i}を引き、自身以下のものの数だけ足す
  • i以上のインデックス向けには、自身より大きいものの数だけ SA _ {i}を引き、自身以下のものの数だけ足す

となることがわかり、結果的には、累積和配列全体をソートし、自身以上のインデックスの分引く、自身未満のインデックスの分足す、とするだけで答えが出ることがわかる。

実装例は以下の通り。
Submission #49840787 - 技術室奥プログラミングコンテスト#6 Day1

あとがき

最初解いたときには、「結果的には...」のところが気づけなくて、座圧+Fenwick木で自身の前後の自分より大きい/小さい要素の数をクソ真面目に数えていました。
記事書きながら思考まとめる最中で、あれこれ条件もっとシンプルにできるんじゃないか、と気づきました。備忘録書くなかでも発見はありますね。