Pythonで最も近い人から少なくともkの距離を確保して立てるかどうかを判定するプログラム

問題の概要

文字列 s と整数 k が与えられます。文字列の各文字は、空きスペースを表すドット（.）か、人がいる位置を表す「x」のどちらかです。このとき、最も近い人との距離が少なくとも k 以上になるような立ち位置を選べるかどうかを判定します。なお、隣接するインデックス間の距離は 1 とします。

例えば、s = "x...x.."、k = 2 の場合、答えは True になります。s[2] または s[6] の位置に立てば、最も近い人との距離がちょうど 2 になるからです。

解法のアプローチ

この問題は、次の手順に従って解くことができます。

1. 文字列 s の中で最初の「x」の位置を pos とします（存在しない場合は -1）。
2. pos が -1（そもそも人がいない）、または pos >= k の場合は、先頭のインデックス 0 に立てるため True を返します。
3. last_x を pos とし、隣接する 2 人の間に必要な最小の空きスペース数 dist_min を 2*k - 1 とします。
4. その後、無限ループの中で以下の処理を繰り返します。
   • last_x + 1 以降で最初に現れる「x」の位置を next_x とします（見つからなければ -1）。
   • next_x が -1 でない場合：2 人の間の空きスペース数（next_x - last_x - 1）が dist_min 以上であれば True を返します。そうでなければ last_x を next_x に更新して処理を続けます。
   • next_x が -1 の場合（last_x が最後の人）：文字列の末尾側の空きスペース数（len(s) - last_x - 1）が k 以上なら True を返し、そうでなければ False を返します。

なぜ dist_min は 2*k - 1 なのか？

隣接する 2 人（位置 last_x と next_x）の間に立ち、双方から距離 k 以上を確保するには、立ち位置 i が「i - last_x >= k」かつ「next_x - i >= k」という 2 つの条件を同時に満たす必要があります。これが成り立つのは next_x - last_x >= 2k のとき、すなわち 2 人の間の空きスペース数が 2k - 1 以上のときです。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
   def solve(self, s, k):
      pos = s.find("x")
      if pos == -1 or pos >= k:
         return True
      last_x = pos
      dist_min = 2 * k - 1
      while True:
         next_x = s.find("x", last_x + 1)
         if next_x != -1:
            if next_x - last_x - 1 >= dist_min:
               return True
            last_x = next_x
         else:
            if len(s) - last_x - 1 >= k:
               return True
            return False

ob = Solution()
print(ob.solve("x...x..", 2))

入力

"x...x..", 2

出力

True

まとめ

このアルゴリズムは文字列を一度だけ走査すればよいため、時間計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。先頭・末尾・隣接する 2 人の間という 3 つのパターンを漏れなくチェックすることで、条件を満たす立ち位置が存在するかどうかを正確に判定できます。