C++でk日間ですべての仕事を完了させる際の難易度合計の最小値を求める方法

問題概要

数値のリスト jobs と整数 k が与えられます。すべての仕事をちょうど k 日間で完了させたいと考えています。ただし、仕事は必ず与えられた順序どおりに実行する必要があり、各日には少なくとも1つのタスクを割り当てなければなりません。

仕事 i の難易度は jobs[i] で表され、ある日の作業全体の難易度は、その日に実行した仕事の中で最も高い難易度となります。つまり、その日の最大値がコストとして加算されます。このとき、k 日間で仕事をすべて完了させるために必要な難易度の合計の最小値を求めてください。

入力例

jobs = [2, 3, 4, 6, 3], k = 2

出力例

8

この場合、1日目に [2] を実行し、2日目に [3, 4, 6, 3] を実行します。難易度の合計は 2 + max(3, 4, 6, 3) = 2 + 6 = 8 となり、これが最小値です。

解決アプローチ:メモ化再帰による動的計画法

この問題は、区間を分割する考え方と動的計画法(DP)を組み合わせることで効率的に解けます。「start 日目以降の仕事を残り k 日で処理するときの最小コスト」を状態として定義し、再帰的に求めます。同じ状態を何度も計算しないよう、結果を dp テーブルにキャッシュするメモ化を行うのがポイントです。

具体的な手順は以下のとおりです。

• サイズ 505 × 15 の2次元配列 dp を定義し、未計算の状態を表す値(-1)で初期化します。
• 関数 dfs(start, k, v) を定義します。引数は開始インデックス start、残りの日数 k、仕事の配列 v です。
• start が配列の末尾に達した場合:k が 0 なら 0(すべての日を使い切ったので成功)、そうでなければ無限大(失敗)を返します。
• k < 0 の場合は無限大を返します(日数を使い切ったのに仕事が残っている状態)。
• dp[start][k] がすでに計算済み(-1 以外)なら、その値を返します。
• ret を無限大、val(現在の区間の最大難易度)を 0 で初期化します。
• i を start から配列末尾まで動かしながらループします。
  • val を v[i] との最大値で更新します(start〜i を1日分として扱う)。
  • ret を「val + dfs(i + 1, k - 1, v)」との最小値で更新します。
• 結果を dp[start][k] に保存して返します。
• メイン側では dp を -1 で初期化し、dfs(0, k, jobs) を呼び出して答えを得ます。

C++での実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e6;
int dp[505][15];

int dfs(int start, int k, vector<int>& v){
    if(start >= v.size()){
        return k == 0 ? 0 : inf;
    }
    if(k < 0)
        return inf;
    if(dp[start][k] != -1)
        return dp[start][k];
    int ret = inf;
    int val = 0;
    for(int i = start; i < v.size(); i++){
        val = max(val, v[i]);
        ret = min(ret, val + dfs(i + 1, k - 1, v));
    }
    return dp[start][k] = ret;
}

int solve(vector<int>& jobs, int k) {
    memset(dp, -1, sizeof dp);
    return dfs(0, k, jobs);
}

int main(){
    vector<int> v = {2, 3, 4, 6, 3};
    int k = 2;
    cout << solve(v, k);
}

実行結果

入力

{2, 3, 4, 6, 3}, 2

出力

8

計算量について

このアルゴリズムの時間計算量は O(n² × k)、空間計算量は O(n × k) です(n は仕事の数)。メモ化により、同じ (start, k) の組み合わせは一度しか計算されないため、全探索の指数オーダーから大幅に改善されます。仕事の数が数百程度、日数が15以下程度の制約であれば十分に高速に動作します。