Codeforces #330 Div1 A. Warrior and Archer
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の11日目のエントリです．
問題概要
- 2人のプレイヤーがゲームをする
- プレイヤー1列のマスにキャラクターを並べて戦う
- 1人はウォーリアーを，1人はアーチャーを使う
- キャラクターの初期位置候補のマスがn (nは偶数)個与えられる
- ウォーリアー側，アーチャー側が交互に残り2個になるまで候補を消去する
- お互いが以下の条件を満たすように最善を尽くす時どの位置が初期位置となるか
- ウォーリアーはできるだけ接近して戦いたい
- アーチャーはできるだけ離れて戦いたい
解法
- まず与えられたマスをソートする
- アーチャー側がウォーリアー側がどこを消去しようが連続する(n-2)/2個のマスを取り除けばその前後のマス以上は離れることができる
- つまりアーチャー側はそのような値が最大となるマスを消去する
- ウォーリアー側はアーチャー側の消去すべきマスを消去しないように消去する
- 従ってi番目のマスとi+(n-2)/2+1番目のマスの差の最大値が答えである
※本番はnは偶数という条件が抜けていてノーコンテストとなったらしい．
