Pythonで都市と最寄り駅の間の最大距離を求めるアルゴリズム

問題概要

N個の都市があり、それぞれ0からN-1までの番号が付けられているとします。さらに、駅が設置されている都市のリストも与えられます。このとき、任意の都市からその最寄りの駅までの距離の最大値を求めるのが目的です。なお、駅のある都市は任意の順序で与えられる可能性がある点に注意してください。

たとえば、入力が N = 6、stations = [2, 4] の場合、出力は 2 になります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• まず、サイズNのブール型リスト station_present を作成し、すべてFalseで初期化します。
• stationsに含まれる各都市について、station_present[city] を True に設定します。
• dist（駅なし都市の連続数）を0、maximum_dist（最大距離）を駅位置の最小値で初期化します。
• 0からN-1までの各都市を走査します。
  • その都市に駅がある場合：maximum_dist を (dist + 1) // 2 と maximum_dist の大きい方で更新し、dist を 0 にリセットします。
  • 駅がない場合：dist を 1 増やします。
• 最後に、maximum_dist と dist の大きい方を返します。

初期値を駅の最小位置とするのは、左端の都市から最初の駅までの距離がこれで表されるためです。また、駅と駅の間にdist個の駅なし都市が連続する場合、その区間における最寄り駅までの最大距離は (dist + 1) // 2 となります。ループ終了後のdistは、最後の駅から右端の都市までの距離を表しています。

Pythonでの実装例

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

def get_max_dist(N, station):
    station_present = [False] * N
    for city in station:
        station_present[city] = True
    dist, maximum_dist = 0, min(station)
    for city in range(N):
        if station_present[city] == True:
            maximum_dist = max((dist + 1) // 2, maximum_dist)
            dist = 0
        else:
            dist += 1
    return max(maximum_dist, dist)

N = 6
station = [2, 4]
print(get_max_dist(N, station))

入力

6, [2, 4]

出力

2

動作の流れ（例：N=6、stations=[2,4]）

都市0と1には駅がないため、distは2まで増加します。都市2に駅があるため、maximum_distは max((2+1)//2, 2) = 2 となり、distは0にリセットされます。続いて都市3でdistが1になり、都市4の駅で再度リセットされます。最後の都市5ではdistが1となるため、結果として max(2, 1) = 2 が返されます。

計算量

このアルゴリズムは都市を一度だけ走査するため、時間計算量は O(N)、空間計算量も O(N) です。都市数が多い場合でも高速に動作する、非常に効率的な解法と言えます。