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

Pocket

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

arank-menu-step6-2a

さっそくアルゴリズムの洗礼を浴びるであろう問題が登場です。私の様なプログラム初心者はここでまず躓くと思います。数学的プログラミング恐ろしい(;’∀’)

解答例

累積和という方法を利用して処理を軽くしなければこの問題は解けません。詳しい説明は「paiza開発日誌」で解説されていますのでこちらの記事を参考にして頂ければと思います。アルゴリズムって難しい(;^ω^)

arank-menu-step6-2

 

この問題の注意点

総和を求める問題ですが、テストケースに「 1 ≦ N, n ≦ 10 ^ 5」という巨大な数値が条件として与えられている為、二重ループを用いて答えを導こうとした場合、タイムオーバーとなります。下記が失敗例のコードです。

 

arank-menu-step6-2b

この事態を回避する為には、上記の通り「累積和」を使いましょう。

エッグ

シェアする

コメントを残す

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

コメントする