paiza スキルチェック過去問題セット「日別訪問者数の最大平均区間 PHP編」解答例

あなたは、とあるウェブサイトを管理していました。
ある連続したk日間、このウェブサイトでキャンペーンを行ったのですが、いつからいつまでの期間に行ったかを忘れてしまいました。

幸い、ウェブサイトを運営していた全n日分のアクセスログが残っており、1日ごとの訪問者数が分かっています。

とりあえず、連続するk日の中で、1日あたりの平均訪問者数が最も多い期間を、キャンペーンを行った期間の候補だと考えることにしました。
n日分の訪問者数のリストとキャンペーンの日数kが入力されるので、キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を出力してください。

paiza スキルチェック過去問題より

この手の問題を考えるとき、頭に浮かぶ図がこれです。

入力例
5 3
1 2 3 2 1

ざっくりしたスプレッドシートで申し訳ありません。

範囲内に連続したかたまりがあり、それが１つずつ横にスライドしている。
スライドできなくなったらそこでおわり。
そういうイメージです。

<?php
    // 自分の得意な言語で
    // Let's チャレンジ！！
    
    /*
    n日分の訪問者数のリストとキャンペーンの日数kが入力されるので、
    キャンペーンを行った期間の候補数と、候補の中で最も早い開始日を出力してください。
    */

    $s = explode(" ",trim(fgets(STDIN)));
    $num = $s[0];//全体の日数
    $cam_num = $s[1];//キャンペーンの日数
    
    $days = explode(" ",trim(fgets(STDIN)));//日ごとの訪問数
    //print_r($day);
    

    //キャンペーン期間の訪問者合計をだす
    for ($i = 0; $i < $num-$cam_num+1; $i++) {
        $sum[$i]=0;//reset 連続するキャンペーン日数の訪問数の合計
        
        for ($j = 0, $k=$i; $j < $cam_num; $j++,$k++) {
            $sum[$i]=$sum[$i]+$days[$k];
        }
    }
    
    //print_r($sum);

    $max = max($sum);
    //echo($max);
    
    $max_num = 0;//reset キャンペーンを行った期間の候補数
    
    //最大値をもっている日程を探す
    foreach($sum as $key=>$value){
        if($value==$max){
            $max_num++;
            $answer[]=$key;
        }
    }
    echo($max_num." ");
    //print_r($answer);
    
    $first_answer = $answer[0]+1;//候補の中で最も早い開始日/配列が０はじまりのため１を足す
    echo($first_answer."\n");
    

?>

構造としては、

• 日にちの訪問者を配列に入れておく($days)
• キャンペーン日数（この場合3日）のかたまり【黄色部分】を１つずつ横にずらして取得したい
• よってforの始まりは$i = 0; 　ループ範囲は$i < $num-$cam_num+1;（全日程numからキャンペーン日数$cam_numを引き１を足す） $i++
• その合計値を配列に入れておく($sum)　（なお$sumのキーはキャンペーン候補開始日にもなっています）
• $sumの最大値をもっているものが「もっともキャンペーンの3日というかたまりのなかで訪問者を取得している」ということになる
• 『キャンペーンを行った期間の候補数』が解答で求められているため、候補日は複数あると仮定し、最大値を持っているものの数を変数に格納($max_num)
• 同時に最大値をもっているもののキー（すなわち開始日候補）を$answerに格納
• 『候補の中で最も早い開始日を出力してください。』ということなので、$answer[0]（配列のトップ）を出したいが、配列は０始まりで日にちは１始まりのため+1して出力

そういう流れになっています。

二重forで処理するのですが内側のforにはちょっと変数に仕掛けがいります。
$j =$i;　でループを始めてしまうと「連続した3日」が、2回目のループの時には「連続した2日」、さらに「連続した1日」と目減りします。これはよくない。
よって$kをかませる必要がありました。

ご参考になれば幸いです。

paiza スキルチェック過去問題セット

https://paiza.jp/works/mondai/skillcheck_archive/problem_index?language_uid=php