【区間の積】STEP: 2 区間和の計算 (paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【区間の積】STEP: 2 区間和の計算 (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 |
<?php $num = trim(fgets(STDIN)); $array = explode(" ",trim(fgets(STDIN))); $arraysum = array(); for($i = 0;$i < $num;$i++){ //累積和の配列を作成する if($i != 0){ array_push($arraysum,$array[$i] + $arraysum[$i-1]); } else { array_push($arraysum,$array[$i]); } } $n = trim(fgets(STDIN)); for($i = 0;$i < $n;$i++){ //累積和を利用して答えを出力 $test = explode(" ",trim(fgets(STDIN))); $a = $test[0]; $b = $test[1]; if($a == 0){ $ans = $arraysum[$b]; } else { $ans = $arraysum[$b] - $arraysum[$a -1]; } echo $ans."\n"; } ?> |
この問題の注意点
総和を求める問題ですが、テストケースに「 1 ≦ N, n ≦ 10 ^ 5」という巨大な数値が条件として与えられている為、二重ループを用いて答えを導こうとした場合、タイムオーバーとなります。下記が失敗例のコードです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
<?php $input = trim(fgets(STDIN)); $array = explode(" ",trim(fgets(STDIN))); $n = trim(fgets(STDIN)); for($i = 0;$i < $n;$i++){ $test = explode(" ",trim(fgets(STDIN))); $ans = 0; $a = $test[0]; $b = $test[1]; for($j = $a;$j < $b + 1;$j++){ $ans += $array[$j]; } echo $ans."\n"; } ?> |
この事態を回避する為には、上記の通り「累積和」を使いましょう。