Official

A - Zombie Editorial by ynymxiaolongbao

\(A_1,\ldots,A_N\) は昇順にソートされているものとし、 \(D_i = A_{i + 1} - A_i\) とします。

以下のような戦略が最適です。

  • \(D_i\) が大きい方からいくつかの \(i\) について、ゾンビ \(i\) とゾンビ \(i + 1\) の中点に餌を置く。
  • その後、左端（位置 \(0\) ）と右端（位置 \(L\) ）に交互に餌を置く。

一つ目のフェーズでいくつの餌を使うかを \(0,1,\ldots,N - 1\) について全て試せば良いです。

計算量は \(O(N \log N)\) です。

最適性の証明

  • \(A_i\) と \(A_i + 1\) の間に餌を置く操作は、一度だけ、中点に置く操作を行うのが良いです。これらの操作で稼げる時間の上限は \((A_{i + 1} - A_i）/2\) でありこれが達成されること、「一度だけ中点に置く」以外の操作を行ったときの \(A_i\) と \(A_i + 1\) の間以外に餌を置く操作は、\(A_i\) と \(A_i + 1\) の間に置く操作をすべて「中点に置く」操作に代替しても可能であることから示せます。
  • \(A_1\) より左、あるいは \(A_N\) より右に餌を置く操作では、位置 \(0\) あるいは \(L\) に餌を置くのが良いです。これらの操作は左右交互に行うのが最適であり、スコアへの寄与を考えることで示すことができます。
  • 「中点に置く操作」より「端に置く操作」を後に行うのが良いです。exchange argumentにより示すことができます。
  • 「中点に置く操作」は、\(D_i\) の大きな地点に行うのが良いです。これは、操作対象とした \(D_i\) の総和が、スコアに正に寄与することから示せます。

posted:
last update: