株式の売買後に所持金を最大化するC++プログラムの解説

問題概要

サイズnの配列Aとサイズmの配列B、そして整数rが与えられます。株を購入できる機会がn回あり、i番目の機会では1株あたりA[i]の価格で好きなだけ株を購入できます。同様に、株を売却できる機会がm回あり、i番目の機会では1株あたりB[i]の価格で好きなだけ株を売却できます。ただし、保有していない株を売ることはできません。
初期所持金がrで保有株がゼロの状態からスタートし、売買を終えた時点での所持金の最大値を求めるのがこの問題の目的です。

具体例

入力が A = [4, 2, 5]、B = [4, 4, 5, 4]、r = 11 の場合を考えてみましょう。このときの出力は 26 になります。
所持金11がある状態で、価格2の株を5株購入すると支出は10、残金は1になります。その後、購入した5株をすべて価格5で売却すれば25を受け取れるため、最終的な所持金は 25 + 1 = 26 となります。これがこのケースにおける最適な行動です。

解法のアプローチ

この問題は貪欲法を用いることで効率的に解くことができます。考え方のポイントは次の通りです。

• 配列Aの中から最も安い購入価格「an」を探します。
• 配列Bの中から最も高い売却価格「bn」を探します。
• bnがanより大きい場合、全財産をanで株に変えて、bnですべて売り切るのが最適です。
• bnがan以下の場合、売買しても利益にならないため、元の所持金rがそのまま答えになります。

なお、初期値 an = 1100 は、想定されるどの株価よりも大きいダミー値(センチネル値)として設定されています。

処理の手順

上記の方針に基づき、以下のステップで処理を進めます。

n := size of A
an := 1100
bn := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
    if an > A[i], then:
        an := A[i]
for initialize i := 0, when i < m, update (increase i by 1), do:
    if bn < B[i], then:
        bn := B[i]
if bn > an, then:
    r := bn * (r / an) + (r - (r / an) * an)
return r

売買後の所持金は「売却した株数 × 最高売却価格 + 端数の残金」で計算されます。r / an の整数除算(切り捨て)によって購入できる株数が決まり、割り切れなかったお金はそのまま手元に残ります。

C++による実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, vector<int> B, int r){
    int n = A.size(), m = B.size();
    int an = 1100, bn = 0;
    for (int i = 0; i < n; i++){
        if (an > A[i])
            an = A[i];
    }
    for (int i = 0; i < m; i++){
        if (bn < B[i])
            bn = B[i];
    }
    if (bn > an){
        r = (bn) * (r / an) + (r - (r / an) * an);
    }
    return r;
}
int main(){
    vector<int> A = { 4, 2, 5 };
    vector<int> B = { 4, 4, 5, 4 };
    int r = 11;
    cout << solve(A, B, r) << endl;
}

入力

{ 4, 2, 5 }, { 4, 4, 5, 4 }, 11

出力

26

まとめ

このアルゴリズムは、それぞれの配列を一度ずつ走査するだけでよいため、時間計算量は O(n + m)、追加メモリ不要で空間計算量は O(1) という非常に効率的な設計です。「最安値で買って最高値で売る」というシンプルな貪欲戦略により、株式売買後の所持金を最大化できます。