全国統一プログラミング王決定戦予選 C - Different Strokes

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c

2人が最適な戦略を取るとき、残っている料理のうち $A_i+B_i$ が最大となるものを交互に選んでいくことになることを示す。

3
20 10
20 20
20 30

この入力の場合を考える。

Aの立場で考えてみよう。 全部相手に料理を食べられてしまった時の自分から見た幸福度の差は、$-B_1-B_2-B_3$ である。料理 $i$ を食べると、この値が $A_i+B_i$ 改善することがわかる。そのため、Aの立場で考えると $A_i+B_i$ が大きいものを優先して食べたいことがわかる。

次にBの立場で考えてみると、同じように $A_i+B_i$ が大きいものを優先するのが最適解であることが同様の議論でわかる。 A も B も料理 $i$ を食べるとそれぞれの立場で見た幸福度の差が $A_i+B_i$ 改善するため、$A_i+B_i$ と書かれた $N$ 個の料理を合計の数値が最大となるよう二人で交互に取り合っているのと同値な状況とみなせる。

$A_i+B_i$ を降順にソートし、奇数番目を高橋くん、偶数番目を青木さんが選んだとして幸福度の差を計算すればOK。

https://atcoder.jp/contests/nikkei2019-qual/submissions/32474436