全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 C - Different Strokes
問題概要
N個の料理には高橋くんと青木さんが感じる美味しさが決まっている。2人とも最終的な自分の獲得した美味しさの総和-相手のそれを最大化するように料理を食べる。最終的な高橋くんの美味しさの総和-青木さんの美味しさの総和を出力する。結構な醜い闘い。
解法
高橋くんが美味しいと思う料理が必ずしも青木さんが美味しいと思う料理ではなく、その逆も考えられることに注意。なんとなく貪欲っぽいなと思う。ここで、例えば高橋くんが美味しさの総和を大きくしたい場合、高橋くんが取ると青木さんが損をするという皿は逐一の状況下で一意に定まる為、A[i]+B[i]をA[i]、B[i]とともに持ってあげて、A[i],B[i]の降順にソートする。そうして配列を順番に見て行き、i%2==0、つまり、高橋くんがとる場合はA[i]、elseならばB[i]をそれぞれ変数に足して、最後に両者の差を出力してあげて、AC。
余談
本番ではA[i]-B[i]でソートして大爆死をかました。ちゃんと考えれば和でやればいいというのが出てきたはずなので悔しい。
