phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

NIKKEI Programming Contest 2019予選 C. Different Strokes

問題

1~Nまで番号が付いたN皿の料理がある。
高橋くんがi番の料理を食べたときはA_iだけ幸福度が増し、青木さんがi番目の料理を食べたときにはB_iだけ幸福度が増す。
高橋くんから、交互に、2人とも「最終的に自分が得る幸福度の総和」-「最終的に相手が得る幸福度の総和」が最大化するように料理を選ぶ。
「最終的に高橋くんが得る幸福度の総和」-「最終的に青木さんが得る幸福度の総和」はいくつになるか。

制約

  • 1 <= N <= 10^5
  • 1<= A_i, B_i <= 10^9

解法

求めたい答えを数式で書いて変形するアプローチを考える。


高橋くんが取る皿の集合をX、青木さんの取る皿の集合をYとすると、
max( Σ_X A_i - Σ_Y B_i )
となる。
このままでは、XとYによって決まる変数だが、
max( Σ_X A_i + (Σ_X B_i - Σ_X B_i) - Σ_Y B_i )
= max( Σ_X (A_i + B_i) - (Σ_X B_i + Σ_Y B_i) )
= max( Σ_X (A_i + B_i) - Σ_すべて B_i )
= max( Σ_X (A_i + B_i) ) - Σ_すべて B_i
とすると、Yを消去することができる。

式の通り、A_i + B_i の和が最大になるようにXを選べばいいので、和でソートして交互に取っていけばよい。