ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 127 F - Absolute Minima

F - Absolute Minima

解法

最適な  x の条件

定数項  b については単に答えに足すだけなので、 a についてだけ考えます。

更新クエリをいくつか処理した後の式

 f(x) = |x-a_{1}| + |x-a_{2}| + \cdots + |x-a_{k}|

を最小にするような  x の値は、 a_{1}, ..., a_{k} の中央値になります。これは以前の記事に説明を書いているのでそちらも参考にしてください。

そのため、この問題は

  • クエリで動的に値  a_{i} を追加しながら、以下の値を求める。
    •  a_{i} の中央値を効率的に求める。
    •  x をその中央値としたときの  f(x) を効率的に求める。

という処理ができれば解けることになります。

ここで、問題文の「最小値を実現する  x が複数存在するときには最小の  x を答える」という要求に注意しておきましょう。要素が奇数個の場合は中央値が厳密に1つなのでこの値を答えれば良いですが、偶数個の場合は中央にある2要素の間ならどこを取っても  f(x) が最小になるので、その2要素のうち小さい方を答える必要があります。要素数 k として、(1-indexedで)小さい方から  \lceil \frac{k}{2}\rceil 番目の要素、ということになります。

中央値の求め方

値を動的に追加/削除しながらその中央値を求める方法はいくつかありますが、私はBIT(Binary Indexed Tree)を使いました。

BITは数列のある1点に値を加算することと、範囲和を求めることができるデータ構造です。これを中央値を求めるために使うことができます。

先ほど見たように今回求めたい中央値は小さい方から  \lceil \frac{k}{2}\rceil 番目の値であり、つまり「  m 以下の要素が  \lceil \frac{k}{2}\rceil 個存在する」という条件を満たす最小の  m ということになります。

つまり値  a_{i} の追加を「BITのインデックス  a_{i} に1を加算する」と処理しておけば、中央値は範囲和を用いて二分探索をすることで求めることができます。

最小値の求め方

次に実際の  f(x) の値です。これもいちいち計算していると間に合いません。

中央値  m が求められたとすると、そこを境に絶対値の符号が逆転します。つまり  a_{i} \lt m のものについては  |m-a_{i}| = m-a_{i} となり、 a_{i} \gt m のものについては  |m-a_{i}| = a_{i}-m となります。

つまりそれぞれの領域ごとに、その総和はある範囲での  a_{i} の総和と  m \times (その範囲にある a_{i} の個数) から求めることができます。ある範囲に存在する  a_{i} の個数は先ほどのBITで求められ、その総和についても「値  a_{i} を追加したときに、BITのインデックス  a_{i} a_{i} を加算する」というBITを別途用意しておけば求められます。

座標圧縮を忘れずに

この解法で解く場合、 a_{i} の値をBITのインデックスにする必要があるので  -10^{9} \le a_{i} \le 10^{9} という制約の大きさがネックになります。これは予め座標圧縮をしておくことで対応することができます。

ACコード

Submission #5607909 - AtCoder Beginner Contest 127