【区間の積】STEP: 5 区間への足し算 (paizaランク A 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【区間の積】STEP: 5 区間への足し算 (paizaランク A 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
テストケースに巨大な数値が設定されており、二重ループを使用した総当たりでの探索はタイムオーバーとなります。処理を軽くするために、この問題では「imos法」を使用しなければなりません。累積和の一種らしいのですが、初めてこの方法を知った時は感動しました。数学ってすげぇなぁ。
解答例
|
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 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; //配列の要素数 $m = $input[1]; //クエリ数 $array = explode(" ",trim(fgets(STDIN))); //配列を作成 $dummy = array(); //「imos法」を行う為のダミー配列作成 for($i = 0;$i < $n;$i++){ //配列の要素数分、0の値を入れる $dummy[$i] = 0; } for($i = 0;$i < $m;$i++){ //「imos法」の区間計算（クエリ仕込み） $test = explode(" ",trim(fgets(STDIN))); $l = $test[0] - 1; //区間の開始地点 $u = $test[1] - 1; //区間の終了地点 $plus = $test[2]; //加算する数値 $dummy[$l] += $plus; //$dummy[$l]に「$plus」を加算し、 if(isset($dummy[$u + 1])){ //$dummy[$u + 1]に「$plus」を減算する（配列の端に出る場合は処理しない） $dummy[$u + 1] -= $plus; } //print_r($dummy); } for($j = 0;$j < $n;$j++){ //累積和を取る if(isset($dummy[$j - 1])){ $dummy[$j] += $dummy[$j - 1] ; } } for($z = 0;$z < $n;$z++){ //「$array」に「$dummy」を足し込む $array[$z] += $dummy[$z]; } for($i = 0;$i < $n; $i++){ //答えを出力する echo $array[$i]."\n"; } ?> |
解答方針
まずこの問題、問題の意味が分かってないとスタート地点にも立てないので一度整理してみましょう。
入力例1を参考に考えてみましょう。
まずこの場合、配列の要素数が「10」、クエリ数「5」、配列は「$array = [1,2,3,4,5,6,7,8,9,10]」が用意されており、合計5回のクエリを実行することで答えを出力します。
クエリの内容は指定された区間の全ての要素に指定された数値を加算しなさいと言うものです。
1回目のクエリを見てみると「1 6 10」となっており、区間1～6番目、すなわち「配列のインデックスキー0～5の要素に10を加算しなさい」という意味になります。
・クエリ1 実行前
・クエリ1 実行後
このような感じで、全てのクエリを実行をした後、全要素を出力する問題です。
ここで注意したいのが、テストケースに非常に大きな数値が設定されており、区間間の要素を加算する時に繰り返し処理を行っていたのではタイムオーバーとなります。
そのため「imos法」を利用し、解答を導きます。
imos法
「imos法」は累積和の一種で、区間の増減を行う際、ダミー配列を用いてループ処理を減らす方法です。
簡単に書きますが、
imos法の手順「必要な要素数のダミー配列（0埋め）の作成」⇒
「クエリを仕込む」⇒
「累積和の処理」⇒
「ダミー配列を足し込む」
「クエリを仕込む」⇒
「累積和の処理」⇒
「ダミー配列を足し込む」
という順序で行っていきます。
必要な要素数のダミー配列を作成する
入力例1を例にして行きます。要素数は10個なので10個の0を持ったダミー配列を作成します。コードで言うなら下記の部分です。
|
1 2 3 4 |
$dummy = array(); //「imos法」を行う為のダミー配列作成 for($i = 0;$i < $n;$i++){ //配列の要素数分、0の値を入れる $dummy[$i] = 0; } |
これでダミー配列が出来上がりました(‘ω’)
クエリを仕込む
|
1 2 3 4 5 6 7 8 9 10 11 12 |
for($i = 0;$i < $m;$i++){ //「imos法」の区間計算（クエリ仕込み） $test = explode(" ",trim(fgets(STDIN))); $l = $test[0] - 1; //区間の開始地点 $u = $test[1] - 1; //区間の終了地点 $plus = $test[2]; //加算する数値 $dummy[$l] += $plus; //$dummy[$l]に「$plus」を加算し、 if(isset($dummy[$u + 1])){ //$dummy[$u + 1]に「$plus」を減算する（配列の端に出る場合は処理しない） $dummy[$u + 1] -= $plus; } //print_r($dummy); } |
累積和の処理
|
1 2 3 4 5 |
for($j = 0;$j < $n;$j++){ //累積和を取る if(isset($dummy[$j - 1])){ $dummy[$j] += $dummy[$j - 1] ; } } |
ダミー配列を足し込む
|
1 2 3 |
for($z = 0;$z < $n;$z++){ //「$array」に「$dummy」を足し込む $array[$z] += $dummy[$z]; } |
