区間和問題の基本と応用〜累積和でスピードアップしよう〜（’I’ の数）

今回は paiza のクエリで「’I’ の数」の問題に挑戦！

前処理で累積和を作っておくことが、効率よく複数の区間和を求める基本であると実感できた！

📘 問題概要

🎯 目的

プレイヤーAとプレイヤーBが、それぞれ教科書の任意の範囲を掴み、その範囲に含まれる アルファベット大文字 ‘I’ の数で勝負する。
複数の対戦（K試合）について、勝敗または引き分けを判定するのが目的。

🔢 入力内容

• 1行目：N K
  • N: 教科書のページ数
  • K: 試合数（ジャッジの回数）
• 次の N 行：各ページに含まれる ‘I’ の数（I_1 ～ I_N）
• 続く K 行：
  各試合について、プレイヤーA・Bの掴んだ範囲のページ番号（1-based index）
  • A_l_i, A_r_i: A が掴んだ区間の開始・終了ページ
  • B_l_i, B_r_i: B が掴んだ区間の開始・終了ページ

⚠️ 特別ルール（反則）

• N / 3 ページ以上を掴んだプレイヤーは反則負け
• 両者とも反則した場合は引き分け（"DRAW"）
• 小数の切り捨てではなく、N / 3は実数として比較

✅ 判定ロジック（1試合ごとに）

A・Bそれぞれの掴んだページ数と、掴んだ範囲に含まれる ‘I’ の合計数を計算

• 反則判定：
  • Aが反則 & Bが反則 → "DRAW"
  • Aが反則のみ "B"
  • Bが反則のみ → "A"

• 正常な勝負：
  • Aの ‘I’ 合計 > "B" → "A"
  • Bの ‘I’ 合計 > "A" → "B"
  • 同じ → "DRAW"

💡 出力形式

各試合ごとに以下のいずれかを1行で出力：

• A：Aの勝ち
• B：Bの勝ち
• DRAW：引き分け

入力例：

10 3
10
9
8
7
6
5
4
3
2
1
1 3 7 10
1 4 3 4
1 5 6 10

出力例：

A
B
DRAW

✅ OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', (input) => lines.push(input));

rl.on('close', () => {
    // 1行目からページ数 N と 試合数 K を取得
    const [N, K] = lines[0].split(' ').map(Number);

    // 各ページごとの 'I' の出現数を配列として取得
    const iCounts = lines.slice(1, N + 1).map(Number);

    // 残りはK試合分のクエリ
    const queries = lines.slice(N + 1);

    // 反則となるページ数の閾値（N / 3）
    const foulThreshold = N / 3;

    for (const q of queries) {
        // A, Bそれぞれの範囲を取得（1-based index）
        const [aStart, aEnd, bStart, bEnd] = q.split(' ').map(Number);

        // ページ数を計算
        const aPages = aEnd - aStart + 1;
        const bPages = bEnd - bStart + 1;

        // 各範囲に含まれる 'I' の合計を求める
        const aTotalI = iCounts.slice(aStart - 1, aEnd).reduce((acc, cur) => acc + cur, 0);
        const bTotalI = iCounts.slice(bStart - 1, bEnd).reduce((acc, cur) => acc + cur, 0);

        // 反則判定
        const aFoul = aPages >= foulThreshold;
        const bFoul = bPages >= foulThreshold;

        if (aFoul && bFoul) {
            console.log('DRAW');
        } 
        else if (aFoul) {
            console.log('B');
        } 
        else if (bFoul) {
            console.log('A');
        } 
        else if (aTotalI > bTotalI) {
            console.log('A');
        } 
        else if (bTotalI > aTotalI) {
            console.log('B');
        } 
        else {
            console.log('DRAW');
        }
    }
});

✨改善コード例（一部）：累積和と区間和

...

// 累積和を構築を追加
const prefixSum = [0];
    for(let i = 0; i < N; i++){
        prefixSum[i + 1] = prefixSum[i] + ICounts[i];
    }

...

// 'I' の合計値を区間和で求める方針に変更
const aTotalI = prefixSum[endA] - prefixSum[startA - 1];
const bTotalI = prefixSum[endB] - prefixSum[startB - 1];

...

• .slice(…).reduce(…) は毎回O(n) → K回の試合で非効率

• prefixSum を使うと、各区間の合計をO(1) で求められる

🗒️まとめ

前処理で累積和を作っておくことが、効率よく複数の区間和を求める基本テクニック！

N = 50000, K = 49997 のテストケース：

• 1つ目のコード： 4.74秒
• 2つ目のコード：0.16秒

という、「各クエリで参照するページ数が多い」かつ、「クエリ数が多い」ほど、実行時間、計算速度に顕著な差がみられた。

原因は、各クエリにおける ‘I’ の合計値 の計算方法・区間和の計算コストの違いによって生じている。

問題のように「区間ごとの合計値を何度も計算する必要がある」場合は、

① あらかじめ累積和を計算しておく
② 各クエリは累積和を使って区間和を定数時間 O(1)で求める

これにより、クエリの数や区間の長さに関係なく、非常に高速に計算できるようにる！！

僕の失敗談(´;ω;｀)と解決法🐈