C++でサイコロの出力シーケンスからプレイヤーの人数を求める方法

問題の概要

文字列 S と数値 X が与えられ、M 人の異なるプレイヤーがサイコロを振るとします。各プレイヤーは、X 以外の数字が出るまでサイコロを振り続けます。文字列 S において、S[i] は i 回目のサイコロの出目を表しており、このときプレイヤーの総人数 M を求めるのが課題です。なお、文字列 S の最後の文字が X になることはないという制約が付いています。

例えば、文字列が「3662123」で X = 6 の場合、出力は 5 になります。これは以下のように説明できます。

• 1人目のプレイヤーが振って 3 を出す
• 2人目のプレイヤーが振って 6、6、2 を出す
• 3人目のプレイヤーが振って 1 を出す
• 4人目のプレイヤーが振って 2 を出す
• 5人目のプレイヤーが振って 3 を出す

解法のアプローチ

この課題は非常にシンプルです。文字列を先頭から順に走査し、X 以外の文字の個数を数えるだけで答えが得られます。「X 以外の数字が出るまで振り続ける」というルールにより、X 以外の数字が現れるたびに一人のプレイヤーのターンが終了すると考えられるためです。

C++による実装例

#include<iostream>
using namespace std;
int countPlayers(string str, int x) {
   int count = 0;
   for (int i = 0; i < str.size(); i++) {
      if (str[i] - '0' != x)
      count++;
   }
   return count;
}
int main() {
   string s = "3662123";
   int x = 6;
   cout << "Number of players: " << countPlayers(s, x);
}

実行結果

Number of players: 5

このアルゴリズムの計算量は O(n)（n は文字列の長さ）であり、非常に効率的です。追加のメモリもほとんど不要なため、実用性の高い実装と言えるでしょう。