AtCoder Regular Contest 131 D - AtArcher
主客転倒
問題
得点は中心に近いほど高い。
D以上の間隔で点をN個まで置く時、得点の合計を最大化せよ
問題を言い換えていきます。
まず隣り合う点の距離はDだとして良いです
なぜなら点集合を密に中心に寄せた方が得点が上がるからです。
また、[-D/2, D/2]に含まれる点が存在するとして良いです。
なぜなら[-D/2, D/2]を跨ぐような2点が存在すると、距離がDより大きくなってしまいますし、それ以外の場合は任意の点が[-D/2, D/2]より左か右に存在する事になりますが、それらを中心に寄せた方が点が高くなるからです。
また左右に偏ると得点が下がるため、この点を中心として良いです。(書いてみると分かりやすいです)
よって、中心の点の位置を決めると点の配置が決まる事になります。
例えば中心が0なら
...-3d -2d -d 0 d 2d 3d ...のようになります
最後に任意の点xについて、xがs点の区間に置かれるような中心の範囲を求め
原点からの中心の距離を添え字とする、いもす法で答えを加算していきます
これは、xが存在する可能性のある任意の区間r(得点s)について
xが区間rに存在するのは中心の位置がa以上b未満の時だというのを求め
中心の位置がa以上b未満の時の答えにsを加算すればよいです。
全ての点について属する区間を決めるのは重そうですが、実際には移動する距離がDまでであるため、ある隣接する区間Ri, Ri+1の境目に置かれる可能性がある点は高々一つしかない事から線形だと分かります。
実装する際は左右に分けて考えるといいです
