スライディングウインドウアルゴリズムを使って問題を解く

# 解いた問題
https://paiza.jp/works/mondai/a_rank_skillcheck_archive/max_range_large
PHPを使って実装しています。

# 解き方
今回は、部分区間や連続したデータの処理を効率よく行うために、スライディングウインドウアルゴリズムを使用しました。このアルゴリズムは、指定した範囲内のデータを少しずつずらしながら処理を行う手法です。
例えば、指定した範囲が２の場合の処理の流れは以下のようになります。

![](https://storage.googleapis.com/zenn-user-upload/e94c542835dc-20250102.png)

今回の問題では、連続するn日の中でk日分の訪問者の**平均そのものを計算する必要はなく**、**最大値が現れる回数と最初の日付を求めること**が求められています。そのため、平均値を求める処理を省略し、合計値の最大を直接計算しています。

# 実装したコード
:::details 実装したコード
```php
$inputInformation = explode(" ", trim(fgets(STDIN)));
$totalDays = intval($inputInformation[0]);
$campaignDays = intval($inputInformation[1]);
$dailyVisitorCounts = explode(" ", trim(fgets(STDIN)));

$result = findMaxCampaignDetails($dailyVisitorCounts, $campaignDays);
// 結果の出力
echo $result['maxCount'] . " " . $result['firstStartDay'] . "\n";

function findMaxCampaignDetails($visitorCounts, $campaignDays) {
  $n = count($visitorCounts);
  $currentSum = array_sum(array_slice($visitorCounts, 0, $campaignDays));
  $maxSum = $currentSum;
  $maxCount = 1; // 最大値が現れる回数
  $firstMaxStartDay = 0;

  // ウインドウをスライドしながら最大値を更新
  for ($i = $campaignDays; $i < $n; $i++) {
      // 新しい日の訪問者数を加え、古い日の訪問者を引く
      $currentSum += $visitorCounts[$i] - $visitorCounts[$i - $campaignDays];

      // 最大値を更新
      if ($currentSum > $maxSum) {
          $maxSum = $currentSum;
          $maxCount = 1; // 新しい最大値なのでリセット
          $firstMaxStartDay = $i - $campaignDays + 1; // 開始位置を更新
      } elseif ($currentSum === $maxSum) {
          $maxCount++; // 同じ最大値がもう1つ見つかった
      }
  }

  return [
      'maxCount' => $maxCount, 
      'firstStartDay' => $firstMaxStartDay + 1 // 1日目を基準
  ];
}
```
:::

# 解説
### 1 入力値の取得
```php
$inputInformation = explode(" ", trim(fgets(STDIN)));
$totalDays = intval($inputInformation[0]);
$campaignDays = intval($inputInformation[1]);
$dailyVisitorCounts = explode(" ", trim(fgets(STDIN)));
```

### 2 訪問者の平均の最大値と回数を計算する
関数の中身の解説をしていきます。
```php
  $n = count($visitorCounts);
  $currentSum = array_sum(array_slice($visitorCounts, 0, $campaignDays));
  $maxSum = $currentSum;
  $maxCount = 1; // 最大値が現れる回数
  $firstMaxStartDay = 0;
```
- `$n`:訪問者数配列の長さを計算します
- `$currentSum`:最初の`campaignDays`分の訪問者数の合計を計算します
- `$maxSum`:現在の最大合計を保持します（初期値は最初の期間の合計）
- `$maxCount`:現在の最大合計が出現した回数を保持します。（初期値は１）
- `$firstMaxStartDay`:最大合計値が最初にあらわれる開始日（インデックスで保持します）

```php
  for ($i = $campaignDays; $i < $n; $i++) {
      // 新しい日の訪問者数を加え、古い日の訪問者を引く
      $currentSum += $visitorCounts[$i] - $visitorCounts[$i - $campaignDays];

      // 最大値を更新
      if ($currentSum > $maxSum) {
          $maxSum = $currentSum;
          $maxCount = 1; // 新しい最大値なのでリセット
          $firstMaxStartDay = $i - $campaignDays + 1; // 開始位置を更新
      } elseif ($currentSum === $maxSum) {
          $maxCount++; // 同じ最大値がもう1つ見つかった
      }
  }
```
新しい日の訪問者数を加え、古い日の訪問者数を引いて、`$currentSum`を更新します。
次の`if`文で`$currentSum`が`$maxSum`より大きい場合には`$maxSum`を更新し、`$maxCount`を1にリセットし、`$firstMaxStartDay`を現在のウインドウの開始日に更新します。
もし、`$currentSum`と`$maxSum`が同じ場合には`$maxCount`をインクリメントします。
```php
  return [
      'maxCount' => $maxCount, 
      'firstStartDay' => $firstMaxStartDay + 1 // 1日目を基準
  ];
```
計算が終わったら、最大値が現れた回数(`$maxCount`)と、最初に現れた開始日(`$firstMaxStartDay`+1)を返却します。

### 3 結果の出力
```php
$result = findMaxCampaignDetails($dailyVisitorCounts, $campaignDays);
// 結果の出力
echo $result['maxCount'] . " " . $result['firstStartDay'] . "\n";
```
最後に結果を出力します。

# おわりに
今回はスライディングウインドウアルゴリズムを使ってPaizaの問題を解きました。実際にどのようにして解いたかなどを言語化すると、理解が十分でない部分などに気づくことができました。引き続きアウトプットを続けていきたいと思います。最後まで読んでいただきありがとうございました。誰かの助けになれば幸いです。