C++で実装する！隣接する生徒の点数に基づくテディ配布数の最小化アルゴリズム

問題概要

N人の生徒と、それぞれの生徒が取得した点数を表す配列が与えられます。学校はこれらの生徒にテディベアを賞品として配布することを決めました。しかし、学校はコストを抑えたいと考えているため、以下の制約条件を満たしながら、配布するテディの総数を最小化することを目標とします。

• すべての生徒は、少なくとも1つのテディを受け取る必要があります
• 隣り合って座っている2人の生徒のうち、点数が高い方の生徒は、低い方の生徒よりも多くのテディを受け取る必要があります
• 同じ点数を持つ2人の生徒は、異なる数のテディを受け取っても構いません

具体例

例として、生徒が3人おり、その点数が次の配列で表されている場合を考えます。

arr[] = {2, 3, 3}
このとき、配布すべきテディの総数は:
{1, 2, 1} つまり合計4個

アルゴリズム

この問題は、動的計画法（DP）を用いて以下の手順で解くことができます。

1. サイズNのテーブルを作成し、すべての要素を1で初期化します（各生徒が最低1つのテディを受け取るため）
2. 点数の配列を走査しながら、以下の処理を行います：
   • a. 現在の生徒の点数が前の生徒より高い場合：
        i. 前の生徒に割り当てられたテディの数を取得する
        ii. その数に1を加えた値を現在の生徒に割り当てる
   • b. 現在の生徒の点数が前の生徒より低い場合：
        i. それ以前に割り当てたすべての値を見直し、必要に応じて修正する

C++での実装例

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int teddieDistribution(int *marks, int n) {
    int table[n];
    fill(table, table + n, 1);
    for (int i = 0; i < n - 1; ++i) {
        if (marks[i + 1] > marks[i]) {
            table[i + 1] = table[i] + 1;
        } else if (marks[i] > marks[i + 1]) {
            int temp = i;
            while (true) {
                if (temp >= 0 && (marks[temp] >
                marks[temp + 1])) {
                    if (table[temp] >
                    table[temp + 1]) {
                        --temp;
                        continue;
                    } else {
                        table[temp] =
                        table[temp + 1] + 1;
                        --temp;
                    }
                } else {
                    break;
                }
            }
        }
    }
    int totalTeddies = 0;
    for (int i = 0; i < n; ++i) {
        totalTeddies += table[i];
    }
    return totalTeddies;
}
int main() {
    int marks[] = {2, 6, 5, 2, 3, 7};
    int totalTeddies = teddieDistribution(marks,
    SIZE(marks));
    cout << "Total teddies to be distributed: " <<
    totalTeddies << "\n";
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Total teddies to be distributed: 12

まとめ

このように、隣接する生徒間の点数比較に基づいて左から右へ走査し、点数が下がる箇所では遡って値を修正する手法により、制約条件を満たす最小限のテディ配布数を効率的に求めることができます。計算量はO(N)程度であり、大規模なデータにも対応可能です。