Pythonでフィニッシュラインに到達するための最小移動回数を求めるプログラム

1次元の道路を車で走行している状況を考えてみましょう。車の現在位置は position = 0、速度は speed = 1 です。この車に対しては、以下の2つの操作のどちらでも実行できます。

• アクセル（加速）: position := position + speed、speed := speed * 2
• バックギア（逆走）: speed > 0 の場合は speed := -1、それ以外の場合は speed := 1

このとき、目標地点（フィニッシュライン）に到達するまでに必要な最小の操作回数を求めるのが本記事の課題です。

たとえば、入力が target = 10 の場合、答えは 7 になります。

解法のアプローチ

この問題は深さ優先探索（DFS）を使って解くことができます。加速とバックギアの組み合わせを再帰的に試しながら、すでに見つかった答えより悪くなる経路を枝刈りすることで、効率的に最短手数を導き出します。具体的な手順は以下の通りです。

• dfs() 関数を定義します。引数として digit（現在の桁数）、cost（累積コスト）、pos（正方向のバックギア使用回数）、neg（負方向のバックギア使用回数）、target（残りの目標距離）を受け取ります。
• tot := cost + max(2 * (pos - 1), 2 * neg - 1) を計算します。
• tot >= ans の場合は、これ以上探索しても改善しないため処理を打ち切ります（枝刈り）。
• target == 0 の場合、ans := min(ans, tot) として答えを更新して終了します。
• step := 2^digit - 1 を計算します。
• step * 2 < |target| の場合は探索を打ち切ります。
• その後、次の5パターンの再帰呼び出しを行います。
  • dfs(digit - 1, cost, pos, neg, target)
  • dfs(digit - 1, cost + digit, pos + 1, neg, target - step)
  • dfs(digit - 1, cost + digit * 2, pos + 2, neg, target - step * 2)
  • dfs(digit - 1, cost + digit, pos, neg + 1, target + step)
  • dfs(digit - 1, cost + digit * 2, pos, neg + 2, target + step * 2)

メイン関数側では、以下のように処理を進めます。

• ans を無限大で初期化します。
• hi := 1 とし、2^hi >= target となるまで hi を増やしていきます。
• dfs(hi, 0, 0, 0, target) を呼び出して探索を開始します。
• 最後に ans を返します。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
    def solve(self, target):
        self.ans = int(1e9)
        hi = 1
        while (1 << hi) < target:
            hi += 1
        self.dfs(hi, 0, 0, 0, target)
        return self.ans

    def dfs(self, digit, cost, pos, neg, target):
        tot = cost + max(2 * (pos - 1), 2 * neg - 1)
        if tot >= self.ans:
            return
        if target == 0:
            self.ans = min(self.ans, tot)
            return
        step = (1 << digit) - 1
        if step * 2 < abs(target):
            return
        self.dfs(digit - 1, cost, pos, neg, target)
        self.dfs(digit - 1, cost + digit, pos + 1, neg, target - step)
        self.dfs(digit - 1, cost + digit * 2, pos + 2, neg, target - step * 2)
        self.dfs(digit - 1, cost + digit, pos, neg + 1, target + step)
        self.dfs(digit - 1, cost + digit * 2, pos, neg + 2, target + step * 2)

ob = Solution()
print(ob.solve(10))

入力

10

出力

7

まとめ

このプログラムでは、DFSによる全探索と枝刈りを組み合わせることで、フィニッシュラインまでの最短操作回数を効率的に求めています。target = 10 の場合、7回の操作でゴールに到達できることが確認できました。加速で一気に距離を稼ぎつつ、オーバーランした分をバックギアで調整するという発想が、この問題の鍵となっています。