C++で解く：カードから取得できる最大ポイントの求め方

複数のカードが一列に並んでおり、各カードにはポイントが割り当てられています。これらのポイントは整数配列 cardPoints として与えられます。各ステップで、列の先頭または末尾からカードを1枚取得でき、ちょうど k 枚のカードを取得しなければなりません。最終的なスコアは、取得したカードのポイントの合計になります。ここでの課題は、整数配列 cardPoints と整数 k が与えられたときに、獲得できる最大スコアを求めることです。

例で理解する

たとえば、入力が cardPoints = [1,2,3,4,5,6,1]、k = 3 の場合、出力は 12 になります。最初の1枚は、左端・右端どちらを取ってもスコアは1です。そこで、先に右端のカードを選ぶことで合計スコアが最大化されます。最適な戦略は右側の3枚を取ることで、最終スコアは 1 + 6 + 5 = 12 となります。

解法のアプローチ

この問題は累積和（プレフィックスサム）を用いることで効率的に解けます。基本的な考え方は、「左端から取る枚数」を0〜k枚の範囲で変化させながら、残りの枚数を右端から取るケースをすべて評価することです。以下の手順に従います。

• 2つの配列 pre1 と pre2 を定義し、元の配列 v で初期化します。
• ret := 0 とします。
• n を配列 v のサイズとします。
• i := 1 から始めて i < n の間、i を1ずつ増やしながら pre1[i] := pre1[i] + pre1[i - 1] を実行し、左からの累積和を作ります。
• i := n - 2 から始めて i >= 0 の間、i を1ずつ減らしながら pre2[i] := pre2[i] + pre2[i + 1] を実行し、右からの累積和を作ります。
• k >= n の場合は、すべてのカードを取得できるため pre1[n - 1] を返します。
• i := k - 1 とし、ret := pre1[i] で初期化します（左端のみからk枚取る場合）。
• i を1減らし、j := n - 1 とします。
• i >= 0 の間、ret := max(ret, pre1[i] + pre2[j]) を計算し、i と j を1ずつ減らします。これは「左から i+1 枚、右から残りを取る」分割を順に試す操作に相当します。
• 最後に ret := max(ret, pre2[n - k]) とします（右端のみからk枚取る場合）。
• ret を返します。

C++による実装例

以下の実装を見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxScore(vector<int>& v, int k) {
        vector<int> pre1(v.begin(), v.end());
        vector<int> pre2(v.begin(), v.end());
        int ret = 0;
        int n = v.size();
        for (int i = 1; i < n; i++) {
            pre1[i] += pre1[i - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            pre2[i] += pre2[i + 1];
        }
        if (k >= n) {
            return pre1[n - 1];
        }
        int i = k - 1;
        ret = pre1[i];
        i--;
        int j = n - 1;
        while (i >= 0) {
            ret = max(ret, pre1[i] + pre2[j]);
            i--;
            j--;
        }
        ret = max(ret, pre2[n - k]);
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,1};
    cout << (ob.maxScore(v, 3));
}

入力

{1,2,3,4,5,6,1}

出力

12

計算量の目安

このアルゴリズムは配列を数回走査するだけで済むため、時間計算量は O(n) です。また、累積和のために2つの補助配列を使用するため、空間計算量も O(n) となります。取得の組み合わせごとに合計を都度計算する非効率な方法と比べ、前計算によって高速化できるのがこの手法の大きなメリットです。