【区間の積】STEP: 5 区間への足し算 (paizaランク A 相当) 解答例 – PHP編【Aランクレベルアップメニュー】

Pocket

【Aランクレベルアップメニュー】 > 【区間の積】STEP: 5 区間への足し算 (paizaランク A 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。

arank-menu-step6-5a

テストケースに巨大な数値が設定されており、二重ループを使用した総当たりでの探索はタイムオーバーとなります。処理を軽くするために、この問題では「imos法」を使用しなければなりません。累積和の一種らしいのですが、初めてこの方法を知った時は感動しました。数学ってすげぇなぁ。

解答例

解答方針

まずこの問題、問題の意味が分かってないとスタート地点にも立てないので一度整理してみましょう。
入力例1を参考に考えてみましょう。
arank-menu-step6-5b

まずこの場合、配列の要素数が「10」、クエリ数「5」、配列は「$array = [1,2,3,4,5,6,7,8,9,10]」が用意されており、合計5回のクエリを実行することで答えを出力します。

クエリの内容は指定された区間の全ての要素指定された数値を加算しなさいと言うものです。
1回目のクエリを見てみると「1 6 10」となっており、区間1~6番目、すなわち「配列のインデックスキー0~5の要素に10を加算しなさい」という意味になります。

・クエリ1 実行前

arank-menu-step6-5c

 

・クエリ1 実行後

arank-menu-step6-5d

このような感じで、全てのクエリを実行をした後、全要素を出力する問題です。
ここで注意したいのが、テストケースに非常に大きな数値が設定されており、区間間の要素を加算する時に繰り返し処理を行っていたのではタイムオーバーとなります。
そのため「imos法」を利用し、解答を導きます。

 

imos法

「imos法」は累積和の一種で、区間の増減を行う際、ダミー配列を用いてループ処理を減らす方法です。
簡単に書きますが、

 

imos法の手順「必要な要素数のダミー配列(0埋め)の作成」⇒
「クエリを仕込む」⇒
「累積和の処理」⇒
「ダミー配列を足し込む」

という順序で行っていきます。

 

必要な要素数のダミー配列を作成する

入力例1を例にして行きます。要素数は10個なので10個の0を持ったダミー配列を作成します。コードで言うなら下記の部分です。

 

これでダミー配列が出来上がりました(‘ω’)
arank-menu-step6-5e

 

クエリを仕込む

ここは慣れないとちょっと難しいのですが、ダミー配列の指定区間の開始地点の要素に「加算する数値」を加算し区間の終了地点+1の要素「加算する数値」を減算します。またこの時、配列端からはみ出す場合は処理をしないことに注意します。この手順をクエリ数繰り返します。

arank-menu-step6-5f

 

累積和の処理

「$dummy[0]の値を$dummy[1]へ加算」、「$dummy[1]の値を$dummy[2]へ加算」、「$dummy[2]の値を$dummy[3]へ加算」…っという感じに処理していきます。
arank-menu-step6-5g

 

ダミー配列を足し込む

ここまで処理したダミー配列の各要素を、元々の配列の要素に足し込むと答えを導くことができます。指定区間内を加算した結果と同じになる訳ですね。初めてここまでできた時はこの方法に感動したものです。よくこんな方法考えることができるなぁ(*’ω’*)

 

arank-menu-step6-5

エッグ

シェアする

コメントを残す

メールアドレスが公開されることはありません。

コメントする