Pythonでn台のバイクが走行できる最大距離を求めるアルゴリズム

問題概要

n台のバイクがあり、それぞれ満タンの状態で100km走行できるものとします。このn台を使って到達できる最大距離を求めるのが本記事の目的です。なお、ここではすべてのバイクが同一仕様であり、1km走行するのに1リットルの燃料を消費すると仮定します。

もしn台すべてが同じ地点から並走した場合、走行できる距離は100kmにとどまってしまいます。そこで目標となるのは、燃料の無駄を最小限に抑えながら最大距離を走ることです。燃料の浪費を減らすということは、言い換えれば実際に動かすバイクの台数を最小化することを意味します。

解決のアプローチ：燃料の中継ぎ戦略

バイクを直列的に運用すれば、より遠くまで進むことができます。具体的には、最後尾のバイクから他のバイクへ燃料を受け渡し、ある時点で最後尾のバイクを切り離します（それ以降は走らせません）。

ここで問題になるのは「どの距離の時点で燃料の受け渡しを行うべきか」という点です。条件は次の2つです。

• 合計走行距離が最大になること
• 残りのバイクの燃料タンクが溢れてしまわないこと

答えはシンプルで、残りn台の状態で fuel/n km を走るごとに1台ずつ切り離していくのが最適です。こうすることで、切り離すバイクの残り燃料を他のバイクの空き容量にちょうど収めることができ、一切の燃料ロスが発生しません。

アルゴリズムの手順

1. covered_distance を 0 で初期化する
2. n > 0 の間、以下を繰り返す
3. covered_distance に fuel / n を加算する
4. n を 1 減らす
5. ループ終了後、covered_distance を返す

この方法では、走行距離は fuel/1 + fuel/2 + … + fuel/n の総和として表されます。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

def maximum_distance(n, fuel):
    covered_distance = 0
    while (n > 0):
        covered_distance = covered_distance + (fuel / n)
        n = n - 1
    return covered_distance

n = 3
fuel = 100
print(maximum_distance(n, fuel))

入力

3, 100

出力

183.33333333333334

結果の解説

n = 3、fuel = 100 の場合、計算は次のようになります。

• 3台で走る区間：100 ÷ 3 ≒ 33.33 km
• 2台で走る区間：100 ÷ 2 = 50 km
• 1台で走る区間：100 ÷ 1 = 100 km

合計すると 33.33 + 50 + 100 = 約183.33 km となり、単純に並走した場合の100kmを大きく上回る結果が得られます。時間計算量は O(n)、空間計算量は O(1) と非常に効率的なアルゴリズムです。