Pythonで等間隔に置かれた石をすべて回収する際の総移動距離を求める方法

問題の概要

あるレース大会が開催されるとしましょう。道路上には複数の石が一直線に並んで置かれており、スタート地点にはバケツが用意されています。バケツから最初の石までは6単位の距離があり、それ以降の石は互いに4単位ずつ離れて配置されています。

参加者はバケツから出発し、最も近い石を拾ってバケツまで戻り、そこに石を入れます。その後、再び走って次の石を取りに行き、また戻ってバケツに入れる——この手順を、すべての石がバケツに収まるまで繰り返します。石がn個あるとき、参加者が移動する必要のある総距離を求めるのがこの問題です。

たとえば入力が n = 5 の場合、出力は 140 になります。これは次の計算によるものです。
2×6 + 2×(6+4) + 2×(6+4+4) + 2×(6+4+4+4) + 2×(6+4+4+4+4) = 140

計算式の導出

まず、各石を回収するために必要な往復距離を整理してみましょう。

• 1個目の石:(6+6)= 2×6 の距離
• 2個目の石:((6+4)+(6+4))= 2×(6+4) の距離
• 3個目の石:((6+4+4)+(6+4+4))= 2×(6+4+4) の距離
• n個目の石:((6+4(n−1))+(6+4(n−1)))= 2×(6+4(n−1)) の距離

これらをすべて足し合わせると、総距離Dは次のように変形できます。

• D = 2×6 + 2×(6+4) + 2×(6+4+4) + … + 2×(6+4(n−1))
• D = 2×[6 + (6+4) + (6+2×4) + … + (6+(n−1)×4)]
• D = 2×[6n + 4(1 + 2 + … + (n−1))]
• D = 2×[6n + 4(n(n−1)/2)]
• D = 2×[6n + 2(n(n−1))]

最終的に、O(1)の計算量で答えを求められるシンプルな閉じた形式の式が得られました。ループを使わずに済むため、nが大きくなっても高速に処理できます。

Pythonでの実装例

それでは、上記の式をPythonで実装してみましょう。

def find_distance(n):
    return 2*(6*n + 2*((n-1)*n))

n = 5
print(find_distance(n))

入力

5

出力

140

まとめ

この問題は、各石への往復距離の規則性を見抜き、等差数列の和の公式を活用することで、効率的に解くことができます。ポイントは「i番目の石までの片道距離が 6 + 4(i−1) で表せる」ことに気づき、全体を因数分解して一般化する流れです。同様のパターンは、配送ルートや巡回収集などの実際の距離計算にも応用できる考え方です。