【C++】軍隊の階級aから階級bへ昇進するのに必要な年数を計算する方法

問題の概要

要素数が n-1 の配列 D と、2つの値 a および b が与えられます。ある軍隊には、1 から n まで番号が付けられた n 個の階級が存在し、階級 i から階級 i+1 に昇進するには D[i] 年かかります。Amal（アマル）は階級 a に到達したばかりですが、彼の目標は階級 b に到達することです。そこで、目標を達成するまでに必要な年数を求めましょう。

例えば、入力が D = [5, 6]、a = 1、b = 3 の場合、出力は 11 になります。これは、階級1から2への昇進に5年、階級2から3への昇進に6年かかるため、合計 5 + 6 = 11 年となるからです。

解決のためのアプローチ

この問題はシンプルなループ処理で解決できます。手順は以下の通りです。

1. 配列 D のサイズを取得します（n = 配列サイズ + 1）。
2. 必要な総年数を格納する変数 s を 0 で初期化します。
3. i を a - 1 から b - 2 までインクリメントしながらループし、各ステップで s に D[i] を加算します。
4. ループ終了後、s を結果として返します。

n := size of D
s := 0
for initialize i := a - 1, when i < b - 1, update (increase i by 1),
do:
    s := s + D[i]
return s

このアルゴリズムの計算量は O(b − a) であり、階級 a から b までの区間のみを走査するため非常に効率的です。

C++での実装例

それでは、実際の実装コードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> D, int a, int b){
    int n = D.size() + 1;
    int s = 0;
    for (int i = a - 1; i < b - 1; i++){
        s = s + D[i];
    }
    return s;
}
int main(){
    vector<int> D = { 5, 6 };
    int a = 1;
    int b = 3;
    cout << solve(D, a, b) << endl;
}

入力

{ 5, 6 }, 1, 3

出力

11

まとめ

このように、配列 D の指定範囲の要素を単純に合計するだけで、階級 a から階級 b への昇進に必要な総年数を簡単に求めることができます。累積和（prefix sum）を事前計算しておけば、複数のクエリに対しても O(1) で回答できるようになるため、応用の幅も広がります。