今回は paiza の「「PV調査」を解くために:part3」の問題に挑戦！
問題概要
- ウェブサイトのアクセスデータから、連続する
k日間の合計訪問者数 を求める問題。 - 与えられた日数
nと訪問者数の配列aに対し、それぞれの区間について次の値を計算する：
b_i = a_i + a_(i+1) + ... + a_(i+k-1) (1 ≦ i ≦ n-k+1)
- これら連続する k 日間の合計訪問者数をすべて求めて、スペース区切りで1行に出力する。
入力例：
8 3 // n k
5 6 2 1 8 5 6 9
出力例：
13 9 11 14 19 20
🔺 タイムアウト
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [n, k] = lines[0].split(' ').map(Number);
const a = lines[1].split(' ').map(Number);
const ans = [];
for (let i = 0; i <= n - k; i++) {
let temp = 0;
for (let j = 0; j < k; j++) {
temp += a[i+j];
}
ans.push(temp);
}
console.log(ans.join(' '));
});
✅ スライドウィンドウ法
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [n, k] = lines[0].split(' ').map(Number);
const a = lines[1].split(' ').map(Number);
const ans = [];
// 最初のk日間の合計
let sum = 0;
for (let i = 0; i < k; i++) {
sum += a[i];
}
ans.push(sum);
// スライドさせながら更新
for (let i = k; i < n; i++) {
sum += a[i] - a[i - k]; // 新しい日を足して、古い日を引く
ans.push(sum);
}
console.log(ans.join(' '));
});
🔍 コードの流れ
- 入力を受け取る
- 最初の
k日分の合計を求める -
sumを次にスライドさせるたびに更新 -
sum += a[i] – a[i – k]
→ 古い日を引き、新しい日を足す - 各段階で
sumを結果配列に追加 - 最後にすべてを出力
📝まとめ
✅ アルゴリズムのポイント
- スライドウィンドウ法を使う。
→ 「前回の合計を再利用」して、次の合計を O(1) で更新できる。 - 単純な二重ループ（O(n×k)）だと、n=300,000 でタイムアウトする。
- スライドウィンドウなら O(n) で処理可能。
✅ コードの流れ
- 入力を受け取る（
n,k,a[]） - 最初の
k日の合計を計算してsumに入れる -
sumを結果配列に追加 - スライドしながら更新
-
sum += a[i] - a[i - k]
（新しい要素を足して、古い要素を引く）
-
- すべての合計値を出力