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

1 min read読了の目安(約700字

問題概要

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

解法

アリスのスコアからボブのスコアを引いたものを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