C++で目標スコアG以上に必要な最小問題数を求めるプログラム

ここでは、それぞれD個の要素を持つ2つの配列 p と c、および整数 G が与えられます。あるプログラミングコンテストでは、各問題は難易度に応じて配点が設定されており、難易度iの問題は1問あたり 100×i 点となります。コンテスト全体の出題数は p[0] + ... + p[D-1] 問です。参加者のtotal_score（合計得点）は、次の2つの要素の合計として定義されます。

• 基本得点： 解いたすべての問題の配点の総和

• ボーナス点： 難易度iの問題をすべて完答すると、基本得点に加えて完全ボーナス c[i] が付与される

Amalはコンテストに初めて挑戦し、まだ1問も解いていません。彼の目標は合計得点をG点以上にすることです。この目標を達成するには、最低でも何問解く必要があるのかを求めます。

たとえば、入力が G = 500、P = [3, 5]、C = [500, 800] の場合、出力は 3 となります。これは、難易度1の問題を3問すべて解くと、基本得点300点に加えてボーナス500点が入り、合計800点となって目標を達成できるためです。

解き方の手順

この問題を解くには、次の手順に従います。

まず、「どの難易度の問題をすべて完答するか」という組み合わせをビット全探索で列挙します。完答しない難易度の中で最も配点の高い問題について、不足分の点数を埋めるのに必要な問題数を計算して部分的に解きます。各パターンで解いた問題数を記録し、G点以上に到達できるパターンの中での最小値を答えとします。計算量は O(2^D × D) であり、難易度の種類Dが小さい場合に有効な手法です。

D := p のサイズ
mi := 10000
for initialize i := 0, when i < 1 << D, update (increase i by 1), do:
   sum := 0
   count := 0
   at := 0
   i のビット値をもとに10ビットの配列 b を初期化
   for initialize j := 0, when j < D, update (increase j by 1), do:
      b の j ビット目が 1 である場合:
         count := count + p[j]
         sum := sum + ((j + 1) * 100 * p[j] + c[j])
      それ以外の場合:
         at := j
   if sum < G, then:
      d := (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100)
      if d <= p[at], then:
         sum := sum + (at + 1) * 100 * d
         count := count + d
   if sum >= G, then:
      mi := min(mi, count)
return mi

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int G, vector<int> p, vector<int> c){
    int D = p.size();
    int mi = 10000;
    for (int i = 0; i < 1 << D; i++){
        int sum = 0;
        int count = 0;
        int at = 0;
        bitset<10> b(i);
        for (int j = 0; j < D; j++){
            if (b.test(j)){
                count += p.at(j);
                sum += (j + 1) * 100 * p.at(j) + c.at(j);
            } else {
                at = j;
            }
        }
        if (sum < G){
            int d = (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100);
            if (d <= p.at(at)){
                sum += (at + 1) * 100 * d;
                count += d;
            }
        }
        if (sum >= G) {
            mi = min(mi, count);
        }
    }
    return mi;
}
int main() {
    int G = 500;
    vector<int> P = { 3, 5 };
    vector<int> C = { 500, 800 };
    cout << solve(G, P, C) << endl;
}

入力

500, { 3, 5 }, { 500, 800 }

出力

3