C++で解くマジックストリング（魔法の文字列）問題

ここでは、「マジックストリング（魔法の文字列）」と呼ばれる特別な文字列 S を扱います。この文字列は '1' と '2' のみで構成され、次のような性質を持っています。

• 文字列 S 内の連続する '1' および '2' の出現回数（ランレングス）を順に並べて連結すると、元の文字列 S 自身が再現されます。
• 文字列 S の先頭部分は次のようになっています。
  S = "1221121221221121122……"
• S の連続する '1' と '2' をグループに分けると、次のようになります。
  1 | 22 | 11 | 2 | 1 | 22 | 1 | 22 | 11 | 2 | 11 | 22 ……
  そして、各グループにおける '1' または '2' の個数を並べると、
  1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2 ……
  となり、これこそが元の文字列 S と一致します。

問題の定義

整数 N が入力として与えられたとき、マジックストリング S の最初の N 文字に含まれる '1' の個数を求めます。

たとえば入力が 6 の場合、マジックストリングの最初の 6 文字は "122112" であり、その中には '1' が 3 つ含まれているため、答えは 3 となります。

解法のアプローチ

この問題は、文字列を先頭から少しずつ伸ばしながら構築することで効率的に解けます。手順は以下のとおりです。

• n <= 0 の場合は 0 を返し、n <= 3 の場合は 1 を返します。
• ret := 1 と初期化し、サイズ n の配列 arr を用意します。
• arr[0] := 1、arr[1] := 2、arr[2] := 2 と設定します。
• head := 2、tail := 3、num := 1 と初期化します。
• tail < n の間、以下を繰り返します。
  • i を 0 から arr[head] − 1 までループさせます。
    • arr[tail] := num を代入します。
    • num が 1 かつ tail < n であれば、ret を 1 増やします。
    • tail を 1 増やします。
    • tail >= n になったら内側のループを抜けます。
  • num = num XOR 3 とすることで、追加する数字を 1 と 2 で交互に切り替えます。
  • head を 1 増やします。
• 最後に ret を返します。

ポイントは、配列自身の値（arr[head]）を使って「次に何個の数字を書き込むか」を決定する点です。これにより、文字列を自己言及的に生成できます。また、XOR 演算（num ^= 3）によって 1 と 2 を簡潔に切り替えられるのも C++ らしい実装です。

C++ 実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int magicalString(int n) {
      if(n <= 0) return 0;
      if(n <= 3) return 1;
      int ret = 1;
      vector <int> arr(n);
      arr[0] = 1;
      arr[1] = 2;
      arr[2] = 2;
      int head = 2;
      int tail = 3;
      int num = 1;
      while(tail < n){
         for(int i = 0; i < arr[head]; i++){
            arr[tail] = num;
            if(num == 1 && tail < n) ret++;
            tail++;
            if(tail >= n) break;
         }
         num ^= 3;
         head++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.magicalString(6));
}

入力

6

出力

3