Codeforces Round #693 (Div. 3) D. Even-Odd Game

問題概要

アリスとボブが数列から交互に数を取り出していって、
アリスはとった数のうち偶数であるようなものの合計、
ボブはとった数のうち奇数であるようなももの合計がスコアになる
両者が最善を尽くしたときに勝つのはどっちか

解法

アリスのスコアからボブのスコアを引いたものを$score$とおく
アリスは$score$を最大化、ボブは$score$を最小化したい
数列のある数$x$について

• 偶数のとき
  • アリスがとったとき: score += x
  • ボブがとったとき: score -= 0
• 奇数のとき
  • アリスがとったとき: score += 0
  • ボブがとったとき: score -= x

このときアリスがとる最善の手は数列の最大のものをとるということになる
数列の最大値が偶数のとき最大値をとればいいのは自明なので、数列の最大値が奇数の場合を考える
数列の最大値を$x_{max}$、数列の中にある偶数のうちの最大のものを$x_{even}$とおく
アリスが$x_{even}$をとればscore += $x_{even}$となるが、
ボブに$x_{max}$をとられてしまう
$x_{max} > x_{even}$であるから、結果としてscoreはマイナスになる
逆にアリスが$x_{max}$をとると
ボブに$x_{odd}$をとられてしまっても$score$は変化しないため、この方が得である

ボブに対しても同様のことが言えるため、数列をソートして大きい順にとっていくのをシミュレーションすればよい

提出コード

https://codeforces.com/contest/1472/submission/105226079