こういう全探索が意外と出てこないという意見はよく聞くよね。
同時に「複数種類の操作を行える問題では、操作の流れを単純化する」という典型思考を試す問題でもある。

問題概要

あなたは誕生日プレゼントとして友人から dequeue D

を貰いました。

deque $D$ は左右に長い筒であり、 $N$ 個の宝石が一列に詰められています。宝石の価値は左から順に $V_1, V_2, ..., V_N$ です。負の価値の宝石が詰められている場合もあります。

はじめ、あなたは 1 つも宝石を持っていません。あなたは、 $D$ に対して以下の 4 種類の操作から 1 つを選んで実行することを $K$ 回まで行うことができます。

操作 A: D に詰められた宝石のうち、左端の宝石を取り出して手に入れる。D が空の場合、この操作を行えない。
操作 B: D に詰められた宝石のうち、右端の宝石を取り出して手に入れる。D が空の場合、この操作を行えない。
操作 C: 持っている宝石を 1 つ選んで D の左端に詰める。宝石を持っていない場合、この操作を行えない。
操作 D: 持っている宝石を 1 つ選んで D の右端に詰める。宝石を持っていない場合、この操作を行えない。

操作終了後に持っている宝石の価値の合計の最大値を求めてください。

制約

$1 \le N \le 50$
$1 \le K \le 100$

考えたこと

こういう操作系の問題では、まずは操作の流れを単純化できないかと考えてみると良さそう。ひとまず

操作 A, B を一通り終えてから
操作 C, D をやっていく

というものだけ考えればよいことはすぐにわかる。A をやって C をやって、また A をやって...というのは完全に無駄だからだ。...ということがわかると、実はもうほとんど解けていて、

左から $a$ 個取り出す
右から $b$ 個取り出す (ここまでで $a + b \le N$ かつ $a + b \le K$ を満たす必要がある)
最大で $\min(K - a - b, a + b)$ 回、取り出したやつを大きい方から筒に再び詰めていく (ただしマイナスのものは詰めなくてよい)

とすれば OK。 $ab$ 通りの場合を調べればよくて、それぞれについて高々 $O(N\log{N})$ 程度の計算量 (取り出した価値のソートが一番時間かかる) で実現できるので、全体として $O(N^{3}\log{N})$ で間に合う。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, K; cin >> N >> K;
    vector<long long> V(N);
    for (int i = 0; i < N; ++i) cin >> V[i];

    long long res = 0;
    for (int p = 0; p <= min(K, N); ++p) {
        for (int q = 0; p + q <= min(K, N); ++q) {
            vector<long long> v;
            long long cur = 0;
            for (int i = 0; i < p; ++i) v.push_back(V[i]), cur += V[i];
            for (int i = 0; i < q; ++i) v.push_back(V[N-1-i]), cur += V[N-1-i];
               
            sort(v.begin(), v.end());
            for (int i = 0; i < min(K - p - q, (int)v.size()); ++i) {
                if (v[i] < 0) cur -= v[i];
            }
            res = max(res, cur);
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 128 D - equeue (水色, 400 点)

問題概要

制約

考えたこと