Pythonで空席から最も近い占有席までの最大距離を求めるプログラム

0と1のみで構成されたリストseatsがあるとします。seats[i]は座席を表しており、値が1ならその座席は使用中(占有)、0なら空席を意味します。ここで、少なくとも1つの空席と1つの占有席が必ず存在するとき、ある空席から最も近い占有席までの距離の最大値を求める問題を考えます。

問題の例

例えば、入力が seats = [1, 0, 1, 0, 0, 0, 1] の場合、出力は 2 となります。これは、空席である seats[4] に座ると、左右どちらの占有席とも距離が2になり、これが最大となるためです。

解決のための手順

この問題は、リストを一度走査するだけで解くことができます。手順は以下の通りです。

• 結果を格納する変数 res を 0 で初期化します。
• 直前に見つけた占有席のインデックスを記録する変数 last を -1 で初期化します。
• n を seats のサイズとします。
• i を 0 から n-1 まで繰り返します。
  • seats[i] が 1(占有席)の場合:
    • res を、「last < 0 ならば i、そうでなければ (i - last) / 2 の切り捨て値」と res のうち大きい方で更新します。
    • last を i に更新します。
• 最後に、res と n - last - 1(末尾側の空席からの距離)の大きい方を返します。

アルゴリズムのポイント

隣接する2つの占有席の間にある空席の距離は、その中間点で最大化されるため、(i - last) // 2 で計算できます。また、先頭側(index 0 から最初の占有席まで)の距離は i、末尾側(最後の占有席から配列の終わりまで)の距離は n - last - 1 となるため、それぞれ別途考慮する必要があります。

実装例(Python)

def solve(seats):
   res, last, n = 0, -1, len(seats)
   for i in range(n):
      if seats[i]:
         res = max(res, i if last < 0 else (i - last) // 2)
         last = i
   return max(res, n - last - 1)

seats = [1, 0, 1, 0, 0, 0, 1]
print(solve(seats))

入力

[1, 0, 1, 0, 0, 0, 1]

出力

2

計算量

このアルゴリズムはリストを一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。