カエルが家にたどり着くための最小ジャンプ回数を求めるC++コード

長さnの2進文字列Sと整数dが与えられます。数直線上で、カエルは地点1から出発し、地点nへの到達を目指しています。カエルは1回のジャンプでd以下の距離だけ右方向へ移動できます。地点1からnまでの各地点には、スイレンの花が咲いていれば「1」、なければ「0」が記されており、カエルはスイレンのある地点にしか着地できません。カエルが地点nに到達するために必要な最小ジャンプ回数を求めましょう。到達が不可能な場合は-1を返します。

例えば、入力が S = "10010101"、d = 4 の場合、出力は 2 になります。これは、位置1(インデックス0)からインデックス4へジャンプし、続けてインデックス7(n番目の地点)へジャンプすることで、合計2回のジャンプで目的地に届くためです。

解き方の手順

この問題は貪欲法(グリーディ法)を用いて解くことができます。具体的な手順は以下の通りです。

• 現在位置xを0(スタート地点)、ジャンプ回数yを0で初期化します。
• 現在位置からd先の地点にスイレン(「1」)がある場合は、そこへジャンプし、カウントを1増やします。
• d先の地点にスイレンがない場合は、スイレンのある地点が見つかるまで1つずつ手前に戻って探します。
• これを目的地(インデックスn-1)に到達するまで繰り返します。
• ジャンプ回数がnを超えた場合は到達不可能と判断し、-1を返します。

n := s のサイズ
x := 0
y := 0
while (x < n - 1 かつ y <= n), do:
    もし s[x] が '1' ならば:
        x := x + d
        y を 1 増やす
    そうでなければ:
        x を 1 減らす
if y >= n, then:
    -1 を返す
それ以外の場合:
    y を返す

実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(string s, int d){
   int n = s.size();
   int x = 0, y = 0;
   while (x < n - 1 && y <= n){
      if (s[x] == '1')
         x += d, ++y;
      else
         --x;
   }
   if (y >= n)
      return -1;
   else
      return y;
}
int main(){
   string S = "10010101";
   int d = 4;
   cout << solve(S, d) << endl;
}

入力

"10010101", 4

出力

2