【区間の積】STEP: 4 最長の区間 (paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【区間の積】STEP: 4 最長の区間 (paizaランク B 相当)
※リンク先へ移動する為には「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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; $m = $input[1]; //この値を越えた時、最大区間を更新していく $array = explode(" ",trim(fgets(STDIN))); //配列作成 $ans = 0; //要素の和を保存する変数 $range = 0; //この変数に答えの最大区間を保存する $a = 0; //区間の始点となる変数 for($i = 0;$i < $n;$i++){ $ans += $array[$i]; //この「$ans」変数に要素の和を格納する if($ans <= $m){ //「$ans」が「$m」の以下の場合 $test = $i - $a; //「$test」に区間を保存する if($test > $range){ //もし「$test」が「$range」より大きかったら $range = $test; //区間の最大値を更新する } } if($i != 0){ //「$i」が0以外で if($ans > $m){ //「$ans」が「$m」のより大きくなった時 $ans -= $array[$a]; //区間の始点位置の要素を「$ans」から減算する $a++; //始点をずらす if($ans <= $m){ //「$ans」の値が「$m」以下になったら $test = $i - $a; //「$test」に区間を保存し if($test > $range){ //もし「$test」が「$range」より大きかったら $range = $test; //区間の最大値を保存する } } while($ans > $m){//「$ans」が「$m」より大きい間、以下の処理を繰り返す $ans -= $array[$a];//区間の始点位置の要素を「$ans」から減算する $a++; //始点をずらす if($ans <= $m){ //「$ans」の値が「$m」以下になったら $test = $i - $a; //「$test」に区間を保存し if($test > $range ){//もし「$test」が「$range」より大きかったら $range = $test; //区間の最大値を保存する } } } } } } ; if($range == 0 && $ans > $m){ //答えを出力する echo "0"; } else { echo $range + 1; } ?> |
