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))))

programming_algorithm/contest_history/atcoder/2018/0120_colocon2018final.txt · 最終更新: 2018/07/25 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0