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

解いた問題

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

解き方

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

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

実装したコード

$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 入力値の取得

$inputInformation = explode(" ", trim(fgets(STDIN)));
$totalDays = intval($inputInformation[0]);
$campaignDays = intval($inputInformation[1]);
$dailyVisitorCounts = explode(" ", trim(fgets(STDIN)));

2 訪問者の平均の最大値と回数を計算する

関数の中身の解説をしていきます。

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

• $n:訪問者数配列の長さを計算します
• $currentSum:最初のcampaignDays分の訪問者数の合計を計算します
• $maxSum:現在の最大合計を保持します（初期値は最初の期間の合計）
• $maxCount:現在の最大合計が出現した回数を保持します。（初期値は１）
• $firstMaxStartDay:最大合計値が最初にあらわれる開始日（インデックスで保持します）

  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をインクリメントします。

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

計算が終わったら、最大値が現れた回数($maxCount)と、最初に現れた開始日($firstMaxStartDay+1)を返却します。

3 結果の出力

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

最後に結果を出力します。

おわりに

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