COLOCON 2018 FINAL
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に投げるに限る。
import bisect
def accumulate():
ans = [0] * n
st = [0] * n
s, t = 0, 0
for i, b in enumerate(barriers):
key = (b, -i)
t = bisect.bisect_left(st, key, lo=s, hi=t)
st[t] = key
s = min(s, t)
t += 1
tmp_r, tmp_ans = 0, float('inf')
for r in range(s, t):
bj, jm = st[r]
cur_ans = bj + (i + jm) ** 2
if tmp_ans >= cur_ans:
tmp_ans = cur_ans
tmp_r = r
ans[i] = tmp_ans
s = tmp_r
return ans
n = int(input())
barriers = list(map(int, input().split()))
ans_f = accumulate()
barriers.reverse()
ans_b = accumulate()
ans_b.reverse()
print('\n'.join(map(str, map(min, ans_f, ans_b))))
