Pythonでn回の反転操作後のボールの位置を求めるプログラム

問題の概要

n個のボールがあり、初期状態では「1, 2, 3, ..., n」の順に並んでいるとします。まずボール全体を反転して「n, n-1, ..., 2, 1」の順序にします。続いて、開始位置を1つ右にずらしながら再度反転を行い、この操作を合計n回繰り返します。毎回、反転の開始位置は前回より1つ右へ移動していきます。

この一連の反転操作が完了した後、最初に「index」番目の位置にあったボールが最終的にどこへ移動するかを求めるのが、この記事で扱う問題です。

具体例

たとえば、balls = 5、index = 2 が入力された場合、出力は 4 になります。ボールの初期状態は次のとおりです。

1, 2, 3, 4, 5

各ステップでの反転結果は以下のように変化していきます。

5,4,3,2,1
5,1,2,3,4
5,1,4,3,2
5,1,4,2,3

この結果から、最初に2番目（0始まり）の位置にあったボールは、最終的に4番目の位置へ移動していることがわかります。

解法の考え方

この問題を実際に反転操作をシミュレーションしながら解くと、計算量はO(n²)になります。しかし、ボールの移動パターンを注意深く観察すると、定数時間O(1)で答えを導き出せることに気づきます。

手順は以下のとおりです。

• index が balls // 2（balls を 2 で割った商の切り捨て値）より小さい場合：2 * index + 1 を返す
• それ以外の場合：2 * (balls - index - 1) を返す

この式が成り立つ理由は、反転操作を繰り返すことで、前半に位置していたボールは奇数番号の位置へ、後半に位置していたボールは偶数番号の位置へ移動するという明確な規則性が生まれるためです。

実装例

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

def solve(balls, index):
   if index < balls // 2:
      return 2 * index + 1
   else:
      return 2 * (balls - index - 1)

print(solve(5, 2))

入力

5, 2

出力

4

まとめ

n個のボールに対して開始位置をずらしながらn回の反転を行う問題では、シミュレーションを実行しなくても、対象のボールが初期状態で前半に位置するか後半に位置するかを判定するだけで、O(1)で最終的な位置を計算できます。このように、規則性のある操作が繰り返される問題では、小さな入力でパターンを観察し数式化することが、効率的なアルゴリズムへの近道となります。