COLOCON 2018 FINAL

COLOCON -Colopl programming contest 2018- Final（オープンコンテスト） - AtCoder

C - スペースエクスプローラー高橋君

• $N$ 個の区画があり、各区画は $a_1,a_2,...,a_N$ の耐久力がある
• $N$ 個の砲門があり、区画のどれか1つを破壊する
• $i$ 番目の砲門で $j$ 番目の区画を破壊するエネルギーは、$a_j+(j-i)^2$
• $N$ 個の各砲門について、区画のどれか1つを破壊するための最小エネルギーをそれぞれ求めよ
• $1 \le N \le 2 \times 10^5$

  区画 a1 a2 a3 a4 a5
耐久力 10 12 16 11  4

  砲門 ↑ ↑ ↑ ↑ ↑
       a1 a1 a5 a5 a5 エネルギー最小のため狙うべき区画
       10 11  8  5  4 必要エネルギー(答え)

左からDP、右からDP、その小さい方を取る。

左からDPすることについて考える。右は配列を逆転させればいい。

左からDPする時、$i$ 番目の砲門については、区画 $1$ ～ $i$ のどれかを破壊する時の最小エネルギーを求める。しかし、全探索してると当然TLE。

「$i$ 番目より左にあるが耐久力が $a_i$ 以上の区画」は、$i$ 番目から右の砲門では狙うことは無い。そこを狙うくらいなら $a_i$ を狙った方が良いから。なので、狙う価値のある区画を更新していく。これは単調増加列となる。

 i 狙う区画候補の耐久値
 1 [10]
 2 [10 12]
 3 [10 12 16]
 4 [10 11]    (a2, a3を狙うくらいならa4を狙った方が常に良い)
 5 [4]

また、$i$ 番目の砲門が狙うべき区画が $j$ 番目となったら、以降で $j-1$ 番目から左の区画を狙うことは無い。

よって候補はさらに減らせる。

 i ※1  ※2     ※1: 左からのDPで確定した狙うべき区画
 1  a1 [10]     ※2: 狙う区画候補の耐久値
 2  a1 [10 12]
 3  a2 [12 16]  (←3番目の砲門はa1よりa2を狙う方が良い。よってa1はこれ以降も狙う対象から外してよい)
 4  a4 [11]
 5  a5 [4]

ただ、pythonだとTLE。より洗練されたアルゴリズムでは通りそうだが、こーいうときは素直にPyPyに投げるに限る。