F - 闇のカードゲーム
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
テーブルの上に、 N 枚のカードが横一列に並べられています(ただし、 N は奇数)。それぞれのカードには正の整数が 1 つずつ書かれており、左から i 番目 (1 \leq i \leq N) のカードに書かれている整数は a_i です。異なるカードに同じ整数が書かれていることはありません。また、カードは、書かれている整数の小さい順に左から並べられています。
すぬけ君といろはちゃんは、テーブルに置かれているカードが 2 枚になるまで、すぬけ君を先手として次の操作を交互に行います。
操作: その時点でテーブルに置かれているカードの中からカードを 1 枚選んで手に取り、その存在を完全に消去する。
操作が全て終了したとき、まだ存在している 2 枚のカードに書かれている整数の差の絶対値を、このゲームのスコアとします。
このゲームには先手・後手ともに追加規則が存在します。
- 先手のすぬけ君は、常に、手番が回ってきた時点で真ん中に置かれているカードを選ばなければなりません。つまり、その時点で残っているカードの枚数を r 枚として、左から (r+1)/2 番目のカードの存在を抹消しなければなりません。
- 後手のいろはちゃんは、手番が回ってきた時点で残っているカードのうち、最も左にあるものか、最も右にあるものを選ばなければなりません。
いろはちゃんが、このゲームのスコアを最小化するように最適に行動するとき、このゲームのスコアがいくつになるかを求めなさい。
制約
- N は奇数、a_i \ (1 \leq i \leq N) は整数
- 3 \leq N \leq 10^{5}
- 1 \leq a_i \leq 10^{9} \ (1 \leq i \leq N)
- a_i < a_j \ (1 \leq i < j \leq N)
入力
入力は以下の形式で標準入力から与えられる。
N a_1\ a_2\ \cdots\ a_N
出力
ゲームのスコアを1行で出力せよ。
入力例1
3 1 5 100
出力例1
99
すぬけ君が、左から 2 番目のカードを消して、ゲームが終了します。
入力例2
9 3 14 15 20 33 51 59 62 68
出力例2
45
解説
解説3ページ目の本文2行目の「最大値」は「最小値」の誤りです。申し訳ございません。
(5/13 21:40 追記)