【スキルチェック過去問題セット 】日別訪問者数の最大平均区間(large) (paizaランク A 相当) 解答例 – PHP編【paiza】
【スキルチェック過去問題セット】 > 日別訪問者数の最大平均区間(large) (paizaランク A 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
「日別訪問者数の最大平均区間」と問題内容は同じですがテストケースが違います。今回出題されるテストケースは非常に大きな数値で出題されており前回と同様のプログラムで制限時間内に間に合わず、クリアすることができません。アルゴリズムを考えて処理を軽くするために、”しゃくとり法”を使って解答を導きます。
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
<?php $input_line = explode(" ",trim(fgets(STDIN))); //print_r($input_line); $alldays = $input_line[0];//記録されている日数 $campaign = $input_line[1];//キャンペーン期間 $sum_array = array(); $test = explode(" ",trim(fgets(STDIN)));//記録されている各日の訪問者数 $copy = $test; $data = array_splice($test,0,$campaign); //print_r($test); //print_r($data); $sum = array_sum($data); array_push($sum_array,$sum); $count = count($test); for($i = 0;$i < $count;$i++){ $sum = $sum + $test[$i] - $copy[$i]; array_push($sum_array,$sum); } $max = max($sum_array); $maxcounter = 0; foreach($sum_array as $value){ if($value == $max){ $maxcounter++; } } $num_campaign = array_search($max,$sum_array)+1; $ans = $maxcounter." ".$num_campaign; echo $ans; ?> |
解答方針
冒頭でお話した通り、前回の解き方だと時間内に間に合わず、クリアすることができません。
巨大な数値に対応する為に”しゃくとり”法という方法で、処理を軽くします。
しゃくとり法
入力例1を参考にしゃくとり法について簡単に説明します。
しゃくとり法は、全区間から指定区間を調べる時、加算と減算を繰り返して区間の総数を調べる方法です。
図のように指定区間の数値を合計します。指定区間を一つずらしたとき、指定区間の末尾を加算し先頭を減算することで区間の総数を記録します。これを全区間の間繰り返し、総数の最も大きな数値を探し出します。それでは各コードを見ていきます。
各情報を取得する
|
1 2 3 4 5 6 7 |
$input_line = explode(" ",trim(fgets(STDIN))); //標準入力から情報を取得する $alldays = $input_line[0]; //記録されている日数 $campaign = $input_line[1]; //キャンペーン期間 $sum_array = array(); //キャンペーン期間中の総数を記録する空配列を作成 $test = explode(" ",trim(fgets(STDIN)));//記録されている各日の訪問者数 $copy = $test; //「$test」の配列を「$copy」にコピーする |
しゃくとり法の準備
|
1 2 3 4 5 |
$data = array_splice($test,0,$campaign); //「$data」に初日からキャンペーン期間日分のデータを、残りを「$test」に分割する $sum = array_sum($data); //初日から指定区間分の総数を求める array_push($sum_array,$sum); // 「$sum_array」に「$sum」を入れる $count = count($test); //「$test」の要素数をカウントする |
しゃくとり法を行う
|
1 2 3 4 |
for($i = 0;$i < $count;$i++){ //しゃくとり法を実行する $sum = $sum + $test[$i] - $copy[$i]; //1つ前の指定区間総和から先頭を減算し、末尾を加算する array_push($sum_array,$sum); //指定区間の総和を「$sum_array」に格納する } |
キャンペーンの候補数と、もっとも早く訪れる候補の開始日を求める
|
1 2 3 4 5 6 7 8 9 10 11 |
$max = max($sum_array); //「$sum_array」から最大値を探す $maxcounter = 0; //最大値が配列内にいくつあるかカウントする変数 foreach($sum_array as $value){ if($value == $max){ $maxcounter++; //最大値の数をカウントする } } $num_campaign = array_search($max,$sum_array)+1; //一番早く訪れるキャンペーン期間候補の日付を探す $ans = $maxcounter." ".$num_campaign; echo $ans; //解答を出力する |
