【ITニュース解説】1518. Water Bottles || LeetCode || C++

「1518. Water Bottles」というプログラミング問題は、手持ちの満タンの水のボトルを飲み干し、その空ボトルを特定のルールで新しい満タンのボトルと交換していく過程で、最終的に飲めるボトルの総数を計算する課題である。例えば、初期に持っている満タンのボトルが何本かあり、空ボトルを数本集めると新しい満タンのボトルと交換できるというルールが与えられる。この交換を繰り返して、最終的に飲めるボトルの合計数を求めるのがこの問題の目的だ。

この問題を解くための直感的な考え方は、手持ちの資源を最大限に活用し、交換可能な限り新しい資源を手に入れるというサイクルを繰り返すことにある。具体的には、まず持っている満タンのボトルをすべて飲み干し、それによって同じ数の空ボトルを得る。次に、その空ボトルが交換に必要な数に達していれば、すぐに交換して新しい満タンのボトルを手に入れる。新しく手に入れたボトルもまた飲み干され、空ボトルとなり、再び交換の機会が生まれる可能性がある。このプロセスは、もはや交換に必要な空ボトルが集まらなくなるまで続けられる。最終的に飲めるボトルの総数は、最初に持っていたボトルと、交換によって手に入れたすべてのボトルの合計となる。

この問題の解決には「貪欲法（Greedy Approach）」と呼ばれる考え方が用いられる。貪欲法とは、各段階でその時点で最も良いと思われる選択（局所最適解）を繰り返すことで、最終的により良い全体的な解（大域最適解）が得られるというアルゴリズムの設計戦略である。この問題の場合、「交換可能な空ボトルがあれば、できるだけ多く交換する」という選択が、その時点での最善手となる。なぜなら、交換できるボトルをすぐに交換することで、新たなボトルを早期に手に入れ、それも飲み干してさらに空ボトルを増やす機会が得られるからである。

具体的なアルゴリズムの手順は次のようになる。まず、初期に持っている満タンのボトルの数を numBottles とする。また、空ボトルを何本集めれば新しい満タンのボトルと交換できるかを示す数を numExchange とする。飲んだボトルの総数を記録するための変数 totalConsumedBottles を用意し、最初は初期の numBottles で初期化する。これがまず最初に飲めるボトルの数だからだ。次に、現在の空ボトル数を表す変数 currentEmptyBottles を用意し、これも最初は初期の numBottles で初期化する。なぜなら、最初の numBottles を飲み干すと、同じ数の空ボトルができるからである。

ここからループ処理に入る。ループは、現在の空ボトル数 currentEmptyBottles が numExchange 以上である限り、つまり交換可能な限り繰り返される。ループの中では、以下の計算を行う。

1. 新しいボトルの獲得数計算: 現在の空ボトル数 currentEmptyBottles を numExchange で割った商を newBottlesObtained とする。これが、このラウンドで新しく交換によって手に入る満タンのボトルの数である。例えば、空ボトルが10本あり、3本で1本交換できる場合、10 / 3 = 3 なので、3本の新しいボトルが手に入る。
2. 残りの空ボトル数計算: 現在の空ボトル数 currentEmptyBottles を numExchange で割った余りを remainingEmptyBottles とする。これは、交換せずに残った空ボトルの数である。上記の例だと、10 % 3 = 1 なので、1本の空ボトルが残る。
3. 飲んだボトルの総数更新: totalConsumedBottles に newBottlesObtained を加算する。新しく手に入れたボトルも飲めるようになるためだ。
4. 次のラウンドの空ボトル数更新: currentEmptyBottles を newBottlesObtained + remainingEmptyBottles に更新する。これは、新しく手に入れた newBottlesObtained 本のボトルを飲み干して空になったボトルと、前のラウンドで交換せずに残っていた remainingEmptyBottles 本の合計が、次の交換ラウンドで利用できる空ボトルの数となるからである。

このループは、currentEmptyBottles が numExchange 未満になり、もはや交換ができなくなるまで繰り返される。ループが終了したら、totalConsumedBottles が最終的に飲んだボトルの総数となるので、この値を返す。

アルゴリズムの効率性を示す指標として、「時間計算量（Time Complexity）」と「空間計算量（Space Complexity）」がある。時間計算量とは、アルゴリズムが実行されるのにかかる時間の目安で、入力サイズに対してどの程度増加するかを示す。この問題の場合、各ループの反復ごとに currentEmptyBottles の値は少なくとも1ずつ減少し、多くの場合 numExchange による除算によって大幅に減少する。最悪の場合でも numBottles の回数程度しかループは実行されないが、実際にはボトル数が急速に減っていくため、より効率的には O(log(numBottles)) と表現される。これは、入力のボトル数が増えても、ループの回数はそれほど増えないことを意味し、非常に高速であることを示唆する。空間計算量とは、アルゴリズムが実行されるのに必要なメモリ量の目安である。このアルゴリズムでは、totalConsumedBottles、currentEmptyBottles、newBottlesObtained、remainingEmptyBottles といった少数の変数のみを使用している。これらの変数の数は入力サイズに関わらず一定であるため、空間計算量は O(1) となる。これは、入力がどれだけ大きくなっても、使用するメモリ量は常に一定で非常に少ないことを意味する。

提供されたC++コードは、上述の貪欲法を実装している。コードでは、numWaterBottles 関数に初期の満タンボトル数 numBottles と交換に必要な空ボトル数 numExchange が渡される。まず、飲んだボトルの総数を記録する変数 totalConsumedBottles を、初期の numBottles で初期化する。次に、while (numBottles >= numExchange) という条件でループを開始する。ここで使用されている numBottles は、関数に渡された初期値であると同時に、ループ内で現在の空ボトル数を表す変数として利用されている。

ループ内部では、まず int newBottlesObtained = numBottles / numExchange; という計算で、現在の空ボトル数から新しく交換で得られる満タンのボトル数を算出する。例えば10本の空ボトルと3本で交換できる場合、3本の新しいボトルが得られる。次に、int remainingEmptyBottles = numBottles % numExchange; で、交換に使われずに残る空ボトル数を計算する。先の例では、1本の空ボトルが残る。 その後、totalConsumedBottles += newBottlesObtained; で、新しく得られたボトルも飲めるため、飲んだボトルの総数に加算する。 そして、numBottles = newBottlesObtained + remainingEmptyBottles; という行で、次の交換ラウンドで使用する空ボトル数を更新する。この計算は、新しく得たボトルを飲み干してできた空ボトル（newBottlesObtained本）と、前のラウンドで交換せずに残っていた空ボトル（remainingEmptyBottles本）の合計を意味する。この更新された numBottles の値で、次のループの条件判定が行われる。 ループは、numBottles、つまり現在の空ボトル数が numExchange 未満になり、これ以上交換ができなくなった時点で終了する。最終的に、関数は totalConsumedBottles の値を返す。このコードは、シンプルなロジックで効率的に問題を解決している。