ロボットの移動文字列を圧縮して最短化するC++コードの解説

長さnの文字列Sを考えます。各文字は「R」または「U」のいずれかです。2次元平面上では、ロボットは右または上に移動でき、「R」なら右へ1マス、「U」なら上へ1マス進みます。しかし、文字列が大きすぎる場合には、これをより短く圧縮したいと考えます。隣接する「RU」や「UR」のようなペアは、斜め移動を表す1文字「D」に置き換えることができます。このとき、最終的に圧縮された文字列の長さを求めるのが本記事の目的です。

例えば、入力が S = "RUURU" の場合を考えてみましょう。先頭の「RU」は「D」に、続く「UR」も「D」に置き換えられ、最後の「U」はそのまま残るため、結果の文字列は「DUD」となります。したがって、出力は 3 になります。

解法の手順

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。文字列を先頭から順に走査し、以下のルールに従います。

• 隣接する2文字が異なる場合（「RU」または「UR」）：それらを1つの斜め移動「D」としてカウントし、インデックスを2つ進めます。
• 隣接する2文字が同じ場合：その文字を1回の移動としてカウントし、インデックスを1つ進めます。

この手順を擬似コードで表すと、次のようになります。

ans := 0
n := size of S
for initialize i := 0, when i < n, update (increase i by 1), do:
   if S[i] is not equal to S[i + 1], then:
      (increase i by 1)
   (increase ans by 1)
return ans

C++での実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(string S){
   int ans = 0;
   int n = S.size();
   for (int i = 0; i < n; ++i){
      if (S[i] != S[i + 1])
         i++;
      ans++;
   }
   return ans;
}
int main(){
   string S = "RUURU";
   cout << solve(S) << endl;
}

入力

"RUURU"

出力

3

アルゴリズムのポイント

このアルゴリズムの計算量はO(n)であり、文字列を一度だけ走査すればよいため非常に効率的です。重要なのは、隣接する異なる文字のペアを見つけたら必ず斜め移動にまとめるという貪欲な選択です。これは、どのような並び方でもペアをまとめることが最終的な文字列の長さを最小化することにつながるため、常に最適な結果が得られます。

また、ループ内で S[i + 1] にアクセスする際、i が最後の文字を指している場合でも、C++のstd::stringは終端のヌル文字（'\0'）を返すため、範囲外アクセスによるエラーは発生せず、正しく動作します。