7K12 blog

猫でも分かるアルゴリズム解説

ABC151 E - Max-Min Sums

f:id:tkr987:20200610125226p:plain

https://atcoder.jp/contests/abc151/submissions/12468410

  • Σ(X- Y) ⇔ ΣX - ΣY
  • max(x)とmin(x)の決め打ち

f:id:tkr987:20200610130605p:plain

素直に実装すると一生処理が終わらないので、線形処理できるように工夫する。max(x)とmin(x)を決め打ちすればf(x)の値が変わらないことに着目しつつ、Σ(X- Y) ⇔ ΣX - ΣYと分解する。数列を昇順に並べたとき、 max(x)=a_iとなるのは [a_1, a_{i-1}]からK-1個選ぶ場合になる。このとき、合計は _{i-1}C_{k-1} \times a_{i}で求まる。min(x)も同様に求める。計算量は O(N)になる。