【C++】累積和で解く！指定範囲内の偶数・奇数の出現確率を求めるクエリ処理

本記事では、指定された範囲に含まれる数値の偶奇（偶数か奇数か）の確率を求める問題を取り上げます。各クエリに対して、確率を p / q の形式で出力することが求められます。

入力 : N = 5, arr[] = { 6, 5, 2, 1, 7 }
query 1: 0 2 2
query 2: 1 2 5
query 3: 0 1 4

出力 : 0
3 4
1 2

この問題では、「そのインデックスまでに出現した偶数の個数」と「奇数の個数」をそれぞれ記録した2つの配列を事前に構築しておきます。こうすることで問題が大幅に単純化され、各クエリに対しては範囲内の該当個数と要素総数から確率を計算して出力するだけで済みます。

解法のアプローチ

このアプローチでは、i番目のインデックスまでに見つかった偶数・奇数の個数をそれぞれ格納する2つの配列を管理し、いわゆる累積和（プレフィックスサム）の考え方を応用して問題を解きます。前処理にO(N)、各クエリへの回答はO(1)で行えるため、クエリが多数ある場合にも効率的に処理できます。

C++実装例

#include <bits/stdc++.h>
using namespace std;
void solve(int arr[], int n, int Q,int query[][3]){
    int even[n + 1]; // i番目までに出現した偶数の個数を数えるための配列
    int odd[n + 1]; // i番目までに出現した奇数の個数を数えるための配列
    even[0] = 0; odd[0] = 0; // 1始まりのインデックスを使用するため、両配列の0番目を0で初期化
    for (int i = 0; i < n; i++) {
        if (arr[i] & 1) { // 奇数ならoddをインクリメント
            odd[i + 1] = odd[i] + 1;
            even[i + 1] = even[i];
        }
        else { // 偶数ならevenをインクリメント
            even[i + 1] = even[i] + 1;
            odd[i + 1] = odd[i];
        }
    }
    for (int i = 0; i < Q; i++) { // 各クエリを走査
        int r = query[i][2]; // 範囲の右端
        int l = query[i][1]; // 範囲の左端
        int k = query[i][0]; // クエリの種類
        int q = r - l + 1; // 指定範囲内の要素数
        int p;
        if (k) // kはクエリの種類。指定範囲内の
            // 同じ偶奇を持つ要素数を求める
            p = odd[r] - odd[l - 1];
        else
            p = even[r] - even[l - 1];
        if (!p) // pが0の場合は単に0を出力
            cout << "0\n";
        else if (p == q) // p == q の場合は1を出力
            cout << "1\n";
        else {
            int g = __gcd(p, q);
            cout << p / g << " " << q / g << "\n"; // pとqに共通因数が残らないよう、最大公約数で約分する
        }
    }
}
int main(){
    int arr[] = { 6, 5, 2, 1, 7 }; // 与えられた配列
    int n = sizeof(arr) / sizeof(int); // 配列のサイズ
    int Q = 2; // クエリの数
    int query[Q][3] = {{ 0, 2, 2 },{ 1, 2, 5 }}; // 与えられたクエリ
    solve(arr, n, Q, query);
    return 0;
}

出力

0
3 4

コードの解説

上記の実装では、まず2つの配列を管理しながら、i番目までに出現した偶数・奇数の個数を累積的に数えています。その後、各クエリに対して差分計算により指定範囲内の偶数（または奇数）の個数 p を求め、範囲内の要素総数 q との比として出力します。p が 0 の場合は「0」、p が q と等しい場合は「1」と出力し、それ以外の場合は __gcd 関数で最大公約数を求めて分数を約分してから出力します。これにより、確率が常に既約分数の形で表されます。

まとめ

本チュートリアルでは、指定範囲内の偶数・奇数の出現確率に関するクエリ処理の解き方を解説しました。累積和を用いた前処理によって各クエリに高速に答えられる点がこの手法の大きな魅力です。紹介したC++プログラムは、C、Java、Pythonなど他の言語でも同様のロジックで実装できます。本チュートリアルが皆さんの学習のお役に立てば幸いです。