C++で2つの数による割り切り条件から利益を最大化する方法

問題の概要

5つの整数 N、A、B、X、Y が与えられます。目標は、1からNまでの範囲の各数について次の条件を確認し、利益を最大化することです。

• ある数が A で割り切れる場合、利益が X 増加します。
• ある数が B で割り切れる場合、利益が Y 増加します。

ただし、同じ数に対して利益を加算できるのは1回だけです。そのため、AとBの両方で割り切れる数については、XとYのうち大きい方を選ぶのが最適戦略となります。

具体例を見てみましょう。

例1

入力: N=4, A=2, B=3, X=2, Y=3

出力: 最大化された利益は 7

説明:

2と4はA（2）で割り切れるため、利益は0→2→4と増加します（X=2を2回加算）。

3はB（3）で割り切れるため、利益は4→7に増加します（Y=3を加算）。

例2

入力: N=5, A=2, B=4, X=1, Y=3

出力: 最大化された利益は 4

説明:

2と4はA（2）で割り切れ、さらに4はB（4）でも割り切れます。

2については利益が0→1に増加し（X=1）。一方、4についてはY（3）の方がX（1）より大きいためBによる割り切りを選択し、利益は1→4に増加します（Y=3を加算）。

アプローチ

この問題は、1からNまでの各数を順に調べるシンプルなシミュレーションで解くことができます。手順は以下の通りです。

• 整数 N、A、B、X、Y を引数として受け取り、最大化された利益を返す関数 maximizeProfit(int n, int a, int b, int x, int y) を定義します。
• 変数 profit に利益の合計を保持します。初期値は0です。
• forループで1からnまでの各数 i について、a および b での割り切りを判定します。
• i が a と b の両方で割り切れる場合は、x と y の大きい方を利益に加算します。
• i が a のみで割り切れる場合は x を加算します。
• i が b のみで割り切れる場合は y を加算します。
• ループ終了後、profit の値を結果として返します。

各数を1回ずつ調べるだけなので、時間計算量は O(N)、追加メモリは不要で空間計算量は O(1) です。

C++実装例

#include <bits/stdc++.h>
using namespace std;

// 最大の利益を返す関数
int maximizeProfit(int n, int a, int b, int x, int y){
    int profit = 0;
    for(int i = 1; i <= n; i++){
        // aとbの両方で割り切れる場合は大きい方を加算
        if(i % a == 0 && i % b == 0){
            int maxx = x >= y ? x : y;
            profit += maxx;
        }
        // aのみで割り切れる場合
        else if(i % a == 0){
            profit += x;
        }
        // bのみで割り切れる場合
        else if(i % b == 0){
            profit += y;
        }
    }
    return profit;
}

int main(){
    int N = 6, A = 2, B = 4, X = 6, Y = 3;
    cout << "Maximized profit is: " << maximizeProfit(N, A, B, X, Y);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Maximized profit is: 18

この結果の内訳は次の通りです。1〜6の範囲で2（A）で割り切れるのは2、4、6の3つです。4は4（B）でも割り切れますが、X=6がY=3より大きいため、いずれの場合も6が加算されます。よって利益は 6＋6＋6＝18 となります。