【区間の積】FINAL問題 区間の積 (paizaランク A 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【区間の積】FINAL問題 区間の積 (paizaランク A 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
めちゃくちゃ難しかった(-_-;)
なんとか通過したものの、解説とかできる気がしません(;^ω^)。STEP3の「最短区間」の「しゃくとり法」を積に直したものなのですが、0が含まれていた時の処理を作らないといけなかったり、注意点が幾つもありなかなか通過できなかった。
解答例
|
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 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; //配列の要素数 $m = $input[1]; //区間の要素積がこの数値を以上だった場合、$rangeに最短区間を保存する $array = explode(" ",trim(fgets(STDIN))); $a = 0; //区間の始点 $ans = 0; //要素積を保存する $range = $n; //答えである最短区間を保存する変数。初期値には要素数を入れておく for($i = 0;$i < $n;$i++){ //要素数分以下の処理を繰り返す if($i == $a){ //区間の始点と終点が同じ場合… $ans = $array[$a] * 1; //始点の値を「$ans」に入れる } elseif($a != $i) { //始点と終点が違う箇所ならば… $ans *= $array[$i]; //これまでの累積値に終点の値をかける } if($ans == 0){ //積の結果が0の場合… $a = $i + 1; //始点を現在の終点+1の箇所へ移動させる $ans = 0; //累積値を0にリセットする continue; //処理のやり直し } if($ans >= $m){ //累積値が「$m」以上になったら $test = $i - $a; //「$test」に「終点-始点」（区間）を保存する if($range > $test){ //「$test」が「$range」より小さかったら $range = $test; //最短区間を保存する } if($i != $a){ //始点と終点が違う箇所ならば… while($ans >= $m){ //累積値が「$m」より小さくなるまで $ans /= $array[$a]; //累積値を始点の値で割る $a++; //始点を1ずらす if($ans >= $m){ //累積値が「$m」以上だったら $test = $i - $a; //「$test」に「終点-始点」（区間）を保存する if($range > $test){ //「$test」が「$range」より小さかったら $range = $test; //最短区間を保存する } } if($i == $a){ //始点と終点が同じ箇所の場合 break; //処理を中断させる } } } } } echo $range + 1; //答えを出力する ?> |
