ABC 128 D equeue

概要

ABC 128 D問題の "equeue" をpythonで解いたのでその解説。
(D問題のequeneで繋げて、Dequeueですね。解いてから気づきました。)

問題

atcoder.jp

入力

N:　リストの長さ K: 操作できる回数 V :整数のリスト(負の値もある)

内容

整数のリストが与えられて、それに対して最大K回まで、以下の４つの操作を一つ選んで実行できる
* A:リストの左端を取り出す
* B:リストの右端を取り出す
* C:手持ちの一つをリストの左端に戻す
* D:手持ちの一つをリストの右端に戻す。
操作を終えた後の、手持ちの整数の合計値を最大化せよ。

解法

ポイント

1. 戻す操作(C,D)は 最後にまとめてやればいい (途中でやると、無駄になるor最後にまとめてやるのと変わらない)
2. 1の時に、 取り出す操作(A,B)の順番は関係なくなる 。(Aを何回行い,Bを何回行うかが大事)
3. 1の時に、戻す操作(C,D)はどっちでも同じなので、 区別がいらない 。

   解法概要

   以上のポイントを踏まえて、AとBの操作の回数をそれぞれ 全探索する 。
   制約が小さいため、全探索が可能。

　解法詳細

1. 取り出す操作(AとBを行う合計回数)をpickとして、ループを回す。
2. 取り出す操作pick回のうち、右から取り出す操作Aを何回を行うかを全探索。
3. 2で、左から取り出す操作の回数も同時に決まる。
4. 実際に取り出す。
5. K-pick回の操作が残ってるので、取り出したリストからできる限り負の値のものを戻す。

   計算量

   R=min{K,N}として、O(R³ logR)

　submittion

# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

ans = 0  # 何もしないと0なので、ansの初期値は0


# pick->取り出す操作をする回数(listより多く取り出さないように注意)
for pick in range(min(K+1, N+1)):
    # 右から取り出す数
    for right in range(pick+1):
        left = pick-right  # 左から取り出す数
        pick_list = V[:right]+V[N-left:]

        # queueに戻す操作
        pick_list = sorted(pick_list)
        tmp_ans = sum(pick_list)  # 戻す前の合計値
        rem = min(K-pick, len(pick_list))  # 戻す操作をできる回数
        for i in range(rem):  # 負の値のものをできるだけ戻す
            if pick_list[i] < 0:
                tmp_ans -= pick_list[i]
            else:
                break
        ans = max(tmp_ans, ans)
print(ans)