C++で解く「レースカー」問題 ― 最短命令列をBFSで求める

問題の概要

無限に続く数直線上で、車は位置 0・速度 +1 の状態からスタートします。車は「A(アクセル:加速)」と「R(リバース:反転)」の2種類からなる命令列に従って自動的に走行します。

命令「A」を受け取ったときの動作

• 位置 := 位置 + 速度、その後 速度 := 速度 × 2

命令「R」を受け取ったときの動作

• 速度が正であれば 速度 := -1
• そうでなければ 速度 := 1

例えば、命令列「AAR」を実行すると、車の位置は 0→1→3→3 と遷移し、速度は 1→2→4→-1 と変化します。

この問題では、目標位置が与えられたとき、そこへ到達するための最短の命令列の長さを求めます。

例として、入力が target = 6 の場合、出力は 5 になります。解のひとつは命令列「AAARA」で、このとき位置は 0→1→3→7→7→6 と遷移します。

解法のアプローチ(幅優先探索)

この問題は、BFS(幅優先探索)を用いて、命令数ごとに状態をレベル別に展開していくことで解くことができます。手順は以下の通りです。

• 訪問済み状態を記録するための集合 visited を定義する
• キュー q を定義し、初期状態 {0, 1} を挿入する
• level を 0 で初期化し、キューが空でない間、level を1ずつ増やしながら以下を繰り返す
  • k をキューの現在のサイズで初期化し、k > 0 の間、k を1ずつ減らしながら以下を処理する
    • キューの先頭要素を curr として取り出し、キューから削除する
    • curr の位置(first)が target と一致していれば、level を返す
    • 前進後の状態を計算する:forward := curr.first + curr.second、forwardSpeed := curr.second × 2
    • key を「forward を文字列化 + "*" + forwardSpeed を文字列化」として生成する
    • forward > 0 かつ |forward − target| < target かつ key が visited に存在しない場合、key を visited に追加し、{forward, forwardSpeed} をキューに挿入する
    • 反転後の状態の key を「curr.first を文字列化 + "*" +(curr.second > 0 なら -1、そうでなければ 1)」として生成する
    • curr.first > 0 かつ |target − curr.first| < target かつ key が visited に存在しない場合、key を visited に追加し、{curr.first, 反転後の速度} をキューに挿入する
• 探索が完了した場合は -1 を返す

枝刈りのポイント

「位置が正であること」と「目標位置との距離が target 未満であること」という条件を設けることで、目標から大きく外れた無駄な状態の展開を防ぎ、探索範囲を効率的に絞り込めます。また、位置と速度の組み合わせを「位置*速度」という文字列キーにして visited で管理することで、同一状態の再探索を回避しています。

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

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int racecar(int target) {
      unordered_set < string > visited;
      queue < pair <int ,int> > q;
      q.push({0, 1});
      for(int level = 0; !q.empty(); level++){
         for(int k = q.size(); k > 0; k-- ){
            pair <int, int> curr = q.front();
            q.pop();
            if(curr.first == target) return level;
            int forward = curr.first + curr.second;
            int forwardSpeed = curr.second * 2;
            string key = to_string(forward) + "*" + to_string(forwardSpeed);
            if(forward > 0 && abs(forward - target) < target && !visited.count(key)){
               visited.insert(key);
               q.push({forward, forwardSpeed});
            }
            key = to_string(curr.first) + "*" + to_string(curr.second > 0 ? - 1: 1);
            if(curr.first > 0 && abs(target - curr.first) < target && !visited.count(key)){
               visited.insert(key);
               q.push({curr.first, curr.second > 0 ? - 1: 1});
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   cout << (ob.racecar(6));
}

入力

6

出力

5