C言語で2ステップで引き出すことができる最大の金額

問題の概要

2つのロッカーL1とL2があり、それぞれコインが入っているものとします。L1にはA枚、L2にはB枚のコインが入っています。このロッカーからコインを引き出し、引き出した合計額を最大化することが目的です。ただし、各ステップでコインを引き出すと、そのロッカーは直前よりも1枚少ない枚数で補充されます。つまり、L1からA枚のコインを引き出せば次はA-1枚に置き換えられ、L2からB枚を引き出せばB-1枚に置き換えられます。

求めたいのは、2ステップ(ちょうど2回の引き出し)で取得できる最大のコイン枚数です。

入力例と出力例

入力: L1 = 10、L2 = 11

出力: 2ステップで引き出せる最大金額 = 21

説明: ステップ1ではL2から11枚のコインを引き出します。すると、L2は11-1=10枚に置き換えられます。ステップ2の時点でL1もL2も10枚ずつなので、どちらから引き出しても結果は同じです。合計は11+10=21枚となり、これが最大値です。

入力: L1 = 5、L2 = 5

出力: 2ステップで引き出せる最大金額 = 10

説明: ステップ1ではL1から5枚のコインを引き出します。すると、L1は5-1=4枚に置き換えられます。ステップ2ではL1が4枚、L2が5枚なので、多い方のL2から5枚を引き出します。合計は5+5=10枚となり、これが最大値です。

アルゴリズムの考え方

• 2つのロッカーL1とL2を整数として扱い、それぞれに入っているコインの枚数を受け取ります。
• 関数 maxMoney(int A, int B) が、ロッカーごとのコイン枚数を引数として受け取ります。
• maxMoney() の中では、最大金額を格納するための変数「money」を用意します。
• まず、moneyにはAとBのうち大きい方の値を代入します(money = A>B ? A : B)。これが最初の引き出しです。
• moneyの値とA・Bを比較することで、どちらのロッカーから引き出したのかを判定します。
• 引き出した側のロッカーを、1枚少ない枚数に置き換えます(A-- または B--)。
• 最後に、再びAとBのうち大きい方の値をmoneyに加算します(money += A>B ? A : B)。これが2回目の引き出しです。

この手法は貪欲法に基づいており、毎回残っているコインが多い方のロッカーを選ぶことで、常に最適な結果が得られます。計算量はO(1)と非常に効率的です。

実装例(C言語)

#include <stdio.h>
#include <math.h>

// 取得できる最大のコイン枚数を返す関数
int maxMoney(int A, int B){
    // 1回目の引き出し:多い方を選ぶ
    int money = A > B ? A : B;
    // 引き出したロッカーを1枚少ない枚数で補充
    if(money == A)
        A--;
    else
        B--;
    // 2回目の引き出し
    money += A > B ? A : B;
    return money;
}

// ドライバーコード
int main(){
    int L1 = 8, L2 = 9;
    printf("Maximum money that can be withdrawn in two steps: %d", maxMoney(L1, L2));
    return 0;
}

実行結果

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

Maximum money that can be withdrawn in two steps: 17

L1=8枚、L2=9枚の場合、まずL2から9枚を引き出し、L2が8枚になった後にもう一方のロッカーから8枚を引き出すため、合計9+8=17枚が最大となります。