C++で繰り返し数字を含む数値の読み上げパターン数を求める方法

本記事では、同じ数字が連続して現れる数値が文字列として与えられたとき、その読み上げ方(綴り方)が何通りあるかを求める方法を解説します。例えば「112233」は「ダブルワン・ダブルツー・ダブルスリー(double one, double two, double three)」とも「ワン・ワン・ツー・ツー・スリー・スリー(one one two two three three)」とも読めます。このように、重複した数字があると読み方が複数存在します。

解法のポイントは、連続する同じ数字のかたまりに注目することです。例えば「13」の場合、読み方は「ワン・スリー」の1通りだけですが、「113」になると「ダブルワン・スリー」と「ワン・ワン・スリー」の2通りが生まれます。つまり、同じ数字がn個連続する区間ごとに 2^(n-1) 通りの選択肢が発生するため、各区間の値を掛け合わせていくのが基本的なアプローチです。

具体的な例で確認してみましょう。

入力例と出力例

例1

入力:

num="11211"

出力:

Count of ways to spell a number with repeated digits are: 4

説明: 読み方は以下の4通りです。

1. One one two one one(ワン・ワン・ツー・ワン・ワン)
2. Double one two one one(ダブルワン・ツー・ワン・ワン)
3. One one two double one(ワン・ワン・ツー・ダブルワン)
4. Double one two double one(ダブルワン・ツー・ダブルワン)

例2

入力:

num="2212"

出力:

Count of ways to spell a number with repeated digits are: 2

説明: 読み方は以下の2通りです。

1. Two two one two(ツー・ツー・ワン・ツー)
2. Double two one two(ダブルツー・ワン・ツー)

プログラムのアプローチ

• 数値を表す文字列 str を受け取ります。
• 関数 word_spell(string str) が文字列を受け取り、読み上げ方の総数を返します。
• 読み上げ方の数を格納する変数 count を 1 で初期化します。
• forループで str の各桁を先頭から順に走査します。
• 変数 temp で特定の数字の連続回数をカウントします。str[i] == str[i+1] が成り立つ間、temp を増加させます。
• 各区間について count = count * pow(2, temp-1) を計算します。
• 最終的な count を結果として返します。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
long long int word_spell(string str){
    long long int count = 1;
    int len = str.length();
    for (int i=0; i<len; i++){
        int temp = 1;
        while(i < len-1 && str[i+1] == str[i]){
            temp++;
            i++;
        }
        count = count * pow(2, temp-1);
    }
    return count;
}
int main(){
    string str = "222211";
    cout<<"Count of ways to spell a number with repeated digits are: "<<word_spell(str);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of ways to spell a number with repeated digits are: 16

この例では「222211」に対して、先頭の「2222」が 2^3 = 8 通り、「11」が 2^1 = 2 通りの読み方を持つため、合計 8 × 2 = 16 通りとなります。計算量は文字列を一度走査するだけで済むため O(n) と効率的で、長い数値文字列でも高速に処理できます。