ARC085 D : ABS(500)
作成日：2017.11.12
最終更新日：2017.11.12
問題概要
$X$,$Y$の2人がゲームをする。
初めはそれぞれ$Z$,$W$が書かれたカードを持っている。
$N$枚ある山札がなくなるまで$X$から交互に操作「山札を上から1枚以上引き、今持っているカードを捨て、最後に引いたカードを持つ」を行う。
山札の上から$i$枚目には$a_i$が書かれており、これは2人とも知っている。
最後に2人が持っているカードに書かれた数の差の絶対値を$X$は最大化、$Y$は最小化するようにした時、この値はいくつになるかを求めよ。
制約
$1 \leq N \leq 2000$
$1 \leq Z,W,a_i \leq 10^9$
入力はすべて整数
考え方
最終的な状態では片方が$a_N$を持っていて、もう片方が$a_i$($i < N$)または$W$を持っている。
最後にカードを引いたのが$X$か$Y$かで場合分けする。
$X$の時、もう片方が$W$ならば$Y$に選択の余地はないのでこの状態はあり得る。
$Y$がカードを引いて$a_i$を持っているならば、$i$$< j$$< N$において$|a_i - a_N|$$\leq |a_j - a_N|$が成り立つ。
しかしそれならば、$X$は$a_j$を持っている状態にしても良い。
$Y$の時、$X$が$a_i$を持っているならば、$i$$< j$$< N$において$|a_i - a_N|$$\geq |a_j - a_N|$が成り立つ。
しかしそれならば、$Y$は$a_j$を持っている状態にしても良い。
以上のことから、答えは$|W-a_N|$または$|a_{N-1} - a_N|$のいずれかであることが分かる。
この選択は$X$ができることから、2つのうちの大きい方が答えである。
ソースコード
マクロ等はこちら
const int MC = 2010;
int N,Z,W;
int a[MC];
int main(){
cin >> N >> Z >> W;
repp(i,1,N+1) cin >> a[i];
a[0] = a[N];
cout << max(abs(W-a[N]),abs(a[N-1]-a[N])) << endl;
return 0;
}解法まとめ
$max(|W-a_N|,|a_{N-1} - a_N|)$が答えである。(9行)