【C++】数値文字列に含まれる偶数の部分文字列の数を数える方法

0〜9の数字からなる長さ n の文字列 S があるとします。部分文字列が表す数値が偶数であるとき、その部分文字列を「偶数の部分文字列」と呼びます。ここでは、文字列 S に含まれる偶数の部分文字列の総数を求める方法を解説します。

たとえば、入力が S = "1234" の場合、出力は 6 になります。偶数となる部分文字列は「2」「4」「12」「34」「234」「1234」の6つ存在するためです。

解法のポイント

数値の偶奇は最後の桁(一の位)だけで決まります。つまり、位置 i にある桁が偶数であれば、その位置で終わるすべての部分文字列は必ず偶数になります。位置 i で終わる部分文字列は開始位置の選び方により i + 1 個存在するため、各偶数の桁ごとに i + 1 を加算していけば答えが求まります。

アルゴリズムの手順

1. 答えを保持する変数 a を 0 で初期化します。
2. 文字列の長さ n を取得します。
3. i = 0 から n − 1 までループし、S[i] が偶数であれば a に i + 1 を加算します。
4. 最後に a を返します。

a := 0
n := S のサイズ
for i := 0 to n-1 do:
    if S[i] mod 2 == 0 then:
        a := a + i + 1
return a

C++での実装例

以下のコードで実際の動作を確認してみましょう。

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

入力

1234

出力

6

計算量

時間計算量:O(n) — 文字列を一度だけ走査すればよいため非常に高速です。
空間計算量:O(1) — 追加のメモリは定数分のみで済みます。

このように、一の位の偶奇に着目することで、全部分文字列を生成せずとも線形時間で問題を解くことができます。