ARC085 D - ABS - ツバサの備忘録

解法

シミュレーションをします。まず、前提として、どちらかはかならず $a_n$ を最後にもっています。
次にXのターンだとします。
このとき、Xは $a_n$ をとってゲームを終わらせることができます。このときの答えをpとしておきます(これは、現在のYの手札と、 $a_n$ の差の絶対値です)。このターンに $a_i$ を選んで手札にするとなると、次のターン相手は $a_{i+1}$ 以降を選ばなければなりません。
しかし、自分が $a_i$ を選び、次のターン相手が $a_j$ を選んだ時に、自分が $a_i$ ではなく $a_n$ を選んだ場合の方がいい結果だった、ということを阻止しなければなりません。
なので、 $a_{i+1}$ 以降で、 $a_n$ との差の絶対値がpより小さいような $a_i$ は存在してはいけません。
これはYについても、大小関係を入れ替えて全く同じことが言えます。
なので、これらをシミュレーションしてターンを繰り返していけば、答えが求まります。
どちらかが $a_{n-1}$ を選んだ時に、次の人が $a_n$ を選んでゲームを終了する条件を書き忘れないようにしましょう。

と、このシミュレーションにはもう1段階続きが存在します。
実は、先ほどの $a_i$ の選び方は、実は最初のXのターンの時点で $a_{n-1}$ か $a_n$ を選ぶ2通りしか存在しません。なので、答えは $O(1)$ で求めることができ、
$max(|w-a_n|,|a_n-a_{n-1}|)$ になります。
これで通したコードはこちらになります。