絶対値ぽまえ絶対許さん
codeFlyer （bitFlyer Programming Contest）オープンコンテスト B - 交通費
まず、問題文を読んで入力を作ります。
制約をよく読むと
()
なので、すでにソートされていることが分かります。制約的にn^2だと間に合わないですし、二分探索を使ってくださいと言っている気がするので、二分探索を使いましょう。
使いどころとしては
X：1 5 10 20 30 、c＝７、d＝3
を例にとると、
｜1-7｜ > 3 ｜20-7| > 3
なのでこの時はd円でよいことが分かります。
つまり、計算すればいいところは
初めて｜Xn - C｜ <= d となるところから ｜Xn - C｜ > d となるところまで
ということが分かります。ここを二分探索で調べます。
しかし、このままではまだ不十分です。よく考えると
X:590 593 633 642 743 859 872 、ｃ=642,d=850108511
のときのようにdがクソデカだと、どうしても すべてのXnについて
｜Xn - C｜ <= d になってしまい、計算量がn^2になってしまいます。
ここで、絶対値の計算する必要ある？と気が付ければこの問題は解けます（僕は気が付けませんでした。つらいね）
はい。絶対値で表記されていますが、別に絶対値のまま計算する必要はないんですね。
というのも、
Xn <= C の時、 ｜Xn - C｜ = C - Xn (例 ｜16 - 64｜ = 64 - 16 = 48)
Xn >= C の時、 ｜Xn - C｜ = Xn - C (例 ｜334 - 57｜ = 334 - 57 = 277)
となるからです。そうすると、
初めて｜Xn - C｜ <= d となるところから ｜Xn - C｜ > d となるところまで
を部分数列Yとすると、
C*(項の数) - 数列YのC以下の数の和 + 数列YのC以上の数の和- C*(項の数)
と(それ以外の項)*dを足せば求められそうです。累積和を使いましょう。
X：590 593 633 642 743 859 872, c=633,d = 20 を例にとると、
｜Xn - C | > d ｜Xn - C｜<= d ｜Xn - C | > d
590 593 <-| 633 642 |-> 743 859 872
｜ 部分数列Y ｜
このような構成になっていることがわかるので、
数列YのC以下の数の和 の求め方を考えるとC以下の項までの和から( | Xn - C | <= d )
になるまでの和を引くと求められそうです。
項の数も、C以下の項の数 - ( | Xn - C | <= d )になるまでの項の数 で求められます。
数列YのC以上の数の和 も同様に ｜Xn - C｜ > d になるまでの和 - C以下の和 で求められて、項の数も同じようにして求められます。
それ以外の項は 数列Xの項の数 - 部分数列Yの項の数 で求められることが分かります
これまた二分探索でC以下の項で一番大きいものを探してやればいいです。
これでこの問題は解決です。
