Codeforces 388(#228 Div1) C. Fox and Card Game
問題
二人がゲームをする。
n個のカードの山があって、i番目の山にはsi枚のカードが積まれていて、上から順にci1, ci2, ..., cisiである。
先手は好きな山を選んで先頭からカードを一枚、後手は好きな山を選んで底からカードを一枚引くというのをカードがなくなるまで繰り返す。
自分が引いたカードの合計が自分の点数で、プレイヤーは自分の点数を最大化したい。
お互いが最善を尽くすとき、先手の点数と後手の点数を出力せよ。
制約条件
n≦100
si≦100
cij≦100
方針
まず全部の山のサイズが偶数だった場合を考えてみる。
この場合、実は、全部si/2枚ずつ取るしかなくなる。
なぜかと言うと、si/2枚より多く取ったほうが先手が有利になる山があったとしたら、
(ゲームの先手+後手の得点は必ずカードの総和となって一定だから)
先手が有利になる=後手が不利になるで、後手はその手を回避しようとしてその山を半分まで取るから。
後手が有利になる山があったとしても先手がsi/2枚取るのでその手は実現しない。
で、結局全部真ん中まで取って終わる。
奇数の山がある場合も基本的に同じで、真ん中よりも向こうを取る手はお互いに絶対実現しないので、
真ん中の取り合いになる。
真ん中の大きい順に先手、後手、先手、後手……と取ってゲームが終了する。
int a[100][100]; int main(){ int n, first = 0, second = 0; vi odd; cin >> n; rep(i, n){ int k; cin >> k; rep(j, k) cin >> a[i][j]; if(k % 2) odd.pb(-a[i][k / 2]); rep(j, k / 2){ first += a[i][j]; second += a[i][k - 1 - j]; } } sort(all(odd)); rep(i, odd.size()){ if(i % 2 == 0) first -= odd[i]; else second -= odd[i]; } cout << first << " " << second << endl; return 0; }