日別訪問者数の最大平均区間(large) スライドウィンドウ

今回は paiza の「日別訪問者数の最大平均区間(large)」の問題に挑戦！

問題概要

• あなたは あるウェブサイトの管理者
• 過去に 連続した k 日間、キャンペーンを行った
• しかし、そのキャンペーン期間がいつだったか分からなくなった

与えられている情報

• サイトを運営していた 全 n 日分のアクセスログが残っている
• 各日について、その日の訪問者数が分かっている
• 入力として与えられるもの：
  • n：運営していた日数
  • k：キャンペーンを行った連続日数
  • a_i：i 日目の訪問者数

キャンペーン期間の仮定ルール

• キャンペーン中はアクセスが増えたはず
• そこで次のように考える：
  • 連続する k 日間の中で
  • 1 日あたりの平均訪問者数が最も多い期間
  • ＝ キャンペーンを行った可能性が高い期間

求めるもの（出力）

• 平均訪問者数が最大となる k 日間の期間について
  • そのような期間が いくつ存在するか
  • その中で 最も早く始まる期間の開始日（1 日目を 1 とする）
• 出力形式：

候補数 開始日

入力例:

5 3
1 2 3 2 1

出力例:

1 2

✅OK例：

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

const lines = [];

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

rl.on('close', () => {
    const [n, k] = lines[0].split(' ').map(Number);
    const a = lines[1].split(' ').map(Number);

    // 最初の k 日間の合計
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += a[i];
    }

    let maxSum = sum;
    let count = 1;
    let start = 1; // 1-indexed

    // スライディングウィンドウ
    for (let i = 0; i < n - k; i++) {
        sum = sum - a[i] + a[i + k];

        if (sum > maxSum) {
            maxSum = sum;
            count = 1;
            start = i + 2;
        } else if (sum === maxSum) {
            count++;
        }
    }

    console.log(count, start);
});

🔍 コードの流れ

• 標準入力から
  • 日数 n
  • キャンペーン日数 k
  • 各日の訪問者数配列 a
    を受け取る
• 最初の k 日間の訪問者数の合計を計算する
  → これを現在の区間和 sum とする
• maxSum にその合計を保存する
• 最大値が出た回数 count を 1 にする
• 最初の開始日 start を 1 日目に設定する（1-indexed）

スライディングウィンドウ部分

• 左端から 1 日ずつ区間を右にずらしていく
• 区間をずらすたびに
  • 左端の日の値を引く
  • 新しく入る右端の日の値を足す
• 新しい区間の合計 sum をチェックする

最大値の判定

• sum がこれまでの最大値 maxSum より大きい場合
  • 最大値を更新
  • 候補数を 1 にリセット
  • 開始日を現在の区間の開始日に更新
• sum が最大値と同じ場合
  • 候補数を 1 増やす

最後に

• 最大平均（＝最大合計）となる
  • 期間の候補数
  • 最も早い開始日
    を出力する

📝まとめ

長さ k の区間を1日ずつずらしながら、合計が最大になる区間を数える。