今回は paiza の「PV調査」の問題に挑戦！
ついに、今までのステップを経て、「PV調査」の本題を解いていく！
📘 問題概要
-
あなたは、あるウェブサイトの訪問者数データを n 日分持っている。
-
しかし、キャンペーンを「連続する k 日間」行ったのですが、いつ行ったか忘れてしまった。
-
そこで、キャンペーン期間中はアクセスが増えるはずなので、
「連続する k 日間の平均訪問者数（＝合計が最大の期間）」をキャンペーン候補とする。
🔍 そのために求めるのは次の2つ：
- 最も平均訪問者数が多くなる期間の数（候補数）
- その中で最も早い開始日（最初の期間）
◯入力
n k
a_1 a_2 ... a_n
-
n: 全日数 -
k: キャンペーン日数（連続する日数） -
a_i: 各日の訪問者数
◯出力
候補数 開始日
入力例:
5 3
1 2 3 2 1
出力例:
1 2
✅ OK例：
const rl = require('readline').createInterface({ input: process.stdin });
// 入力行を格納する配列
const lines = [];
// 1行ずつ読み取って lines 配列に格納
rl.on('line', (input) => lines.push(input));
// 入力がすべて終わったら処理を開始
rl.on('close', () => {
// ---------- 入力の分解 ----------
const [n, k] = lines[0].split(' ').map(Number); // n: 日数, k: 連続日数
const a = lines[1].split(' ').map(Number); // 各日の訪問者数（配列）
// ---------- 初期設定 ----------
let logs = []; // 各 k 日間の合計値を記録する配列
let sum = 0; // 現在の k 日間の合計値
// 最初の k 日間の合計を計算
for (let i = 0; i < k; i++) {
sum += a[i];
}
logs.push(sum); // 最初の区間の合計を保存
let max = sum; // 現時点の最大合計値
let day = 1; // 最大合計値となる最初の開始日（1始まり）
// ---------- スライドウィンドウで合計を更新 ----------
// 「新しい1日分を足し、古い1日分を引く」ことで効率よく次の区間の合計を求める
for (let i = k; i < n; i++) {
sum += a[i] - a[i - k];
logs.push(sum);
}
// ---------- 最大合計値と最初の開始日を探索 ----------
for (let i = 0; i < n - k + 1; i++) {
if (logs[i] > max) {
max = logs[i]; // 新しい最大値を更新
day = i + 1; // 1始まりで開始日を記録
}
}
// ---------- 最大値が出現する回数（候補数）をカウント ----------
const num = logs.filter(x => x === max).length;
// ---------- 結果出力 ----------
// 出力形式：「候補数 最大値となる最初の開始日」
console.log(num, day);
});
💻 コードの流れ
- 入力を受け取る
- 1行目：
n（全日数）とk（連続日数）を取得 - 2行目：
a（各日の訪問者数の配列）を取得
- 1行目：
- 初期設定
-
logs = []：各「k日間の合計」を記録するための配列 -
sum = 0：現在のk日間の合計を計算用に初期化
-
- 最初の
k日間の合計を求めるfor (let i = 0; i < k; i++) sum += a[i];- 最初の区間の合計を
logsに記録 - これを初期最大値
maxに設定 -
day = 1（最初の開始日を1日目として設定）
- スライドウィンドウで全区間を求める
-
for (let i = k; i < n; i++)- 新しい日
a[i]を足して - 古い日
a[i - k]を引く
→ これで次の区間の合計が求まる
- 新しい日
- 求めた合計を l
ogsに順に追加
-
- 最大合計値とその最初の開始日を探す
for (let i = 0; i < n - k + 1; i++)-
logs[i] > maxのとき
→ 新しい最大値を発見
→maxを更新し、day = i + 1（1始まり）
- 最大値が何回出現したかを数える
const num = logs.filter(x => x === max).length;- 最大合計値を持つ期間の候補数を求める
- 結果を出力
console.log(num, day);- 表示形式：
→ 「候補数（最大期間の数）」＋「最初の開始日」
✅ logs を省略
let max = sum;
let count = 1;
let day = 1;
for (let i = k; i < n; i++) {
sum += a[i] - a[i - k];
if (sum > max) {
max = sum;
count = 1;
day = i - k + 2;
} else if (sum === max) {
count++;
}
}
console.log(count, day);
🎯 学習のまとめ
🧮 アルゴリズムの考え方
- 平均最大 = 合計最大（
kは一定なので平均の大小は合計の大小と同じ） - 「連続する
k日間の合計」をすべて調べる必要がある
→ スライドウィンドウ法を使うことで高速に処理できる
⚡ スライドウィンドウ法の流れ
- 最初の
k日間の合計を求める - 次の日に移るごとに「新しい日を足し、古い日を引く」
→ O(n) で全期間の合計を計算できる - 合計が最大の値を更新・記録していく
📊 出力に必要な情報
-
max：これまでの最大合計値 -
count：最大値と同じ合計の期間の数 - day`：最大値を最初に記録した開始日（1始まり）
💡 実装のコツ
-
i - k + 2：インデックスを1始まりに直す（開始日を正しく出すため） - 合計更新は
sum += a[i] - a[i - k] - 配列を全て保存せずに（
logsなし）変数だけで十分に解ける