全統2019予選-D "Different Strokes"
提出コード
atcoder.jp
考察
「最終的に高橋くんが得る幸福度の総和」ー「最終的に青木さんが得る幸福度の総和」とおきます．
問題の条件より，
人は以下のような行動をします．
高橋くん：
を最大化する
青木さん：を最小化する．
これを踏まえると，それぞれが
番目の料理を食べたとき，状況を以下のように変化させることができます．
高橋くん： を 
]増やす(青木さんはを
]減らす権利を失う)
青木さん： を ]減らす(高橋くんはを ]増やす権利を失う)
高橋くん目線で考えます．
高橋くんは増やす分の ]はできるだけ大きく取りたいし，青木さんが減らす権利を失う分の ]もできるだけ大きく取りたいです．
]の値が大きいほど，青木さんがを減らせる度合いは小さくなるためです．
青木さんも同様で，減らす分の ]はできるだけ大きく取りたいし，高橋くんが増やす権利を失う分の ]もできるだけ大きく取りたいです．
つまり高橋くんから始めて，それぞれは
]
]が大きいものから選んで料理を食べていけばいいです．
実装としては，例えば ] ]とをペアで持たせて， ] ]で降順にソート．
] ]が大きいindexから順に，
] (高橋くんが料理を食べる)
] (青木さんが料理を食べる)
] (高橋くんが料理を食べる)
とすれば答えが
で出ます．
感想
最近の問題ABC187-Dにかなり似ていますね．
これをやっていた分解きやすかったです．
