ABC128 D - equeue

問題原文

atcoder.jp

問題要旨

価値がそれぞれ であるような宝石が 個入った筒 が与えられる。この筒に対して、 回まで以下の操作のうち１つを選んで行う。

• の左端から宝石を取り出す。
• の右端から宝石を取り出す。
• 手持ちの宝石のうち１つを の左端に詰める。
• 手持ちの宝石のうち１つを の右端に詰める。

手持ちの宝石の価値を最大化せよ。

• 入力は全て整数。
• 
• 
• 

解法

実装が爆発しそうな雰囲気。 最大化したいのはあくまでも「最終的手元に残った宝石の価値の合計」なことに注意する。

取り出す途中で宝石をどこかに詰めるより、一旦取り出すだけ取り出しておいて、最後に不要なものを詰めるとして明らかに損しない。 ということで、手元にたくさん宝石を集めて、不要なものを筒に詰め直すことを考える。
当然筒の詰め方はどうでもいい。（不要な宝石を「捨てる」とも言い換えられる）

のように、「損を承知でとった方がいい場合がある」ことに気づく。
ここで貪欲法は捨てることになる。

制約が小さいので、「何個取り出すことにするか」が探索できる。これは （）。
「何個左から取り出すか（何個右から取り出すか）」も全探索できる。これで [tex: O(R²)]。
手元に宝石を集めたら、明らかに価値が小さい負のものから捨てていけばいいことはわかる。ソートが必要なので、これで 。
制約が小さいので間に合う。

実装

N, K = map(int, input().split())
V = list(map(int, input().split()))

# 最終的に「持っているもの」の価値の合計を高めたい
# Dから取り出すことをpop、Dに詰めることをenqueueとする
ans = 0
# 何個取り出すことにするかを探索
for pop_cnt in range(K + 1):
    enqueue_cnt = K - pop_cnt

    if pop_cnt > N:
        continue
    
    # 何個左から取り出すことにするかを探索
    for l in range(pop_cnt + 1):
        holding = []

        r = pop_cnt - l
        holding += V[:l]
        holding += V[N - r:]

        # 価値が負のものを小さい順に捨てられるだけ捨てる
        holding.sort()
        tmp_ans = sum(holding)

        for e in range(enqueue_cnt):
            if e >= len(holding):
                break

            if holding[e] < 0:
                tmp_ans += -holding[e]

        ans = max(ans, tmp_ans)

print(ans)

感想

こういう問題はとても好み。
毎回 左/右からから取り出す宝石は１個ずつしかずれないので、それを利用すると で解けるらしい。