paizaのPOH Lite4を解くのに必要な「累積和」について | Select *
コンピュータ

paizaのPOH Lite4を解くのに必要な「累積和」について

programing初めてPOHにチャレンジした@deepblue_willです。

プログラマーならお馴染みのコード転職paizaで定期的に開催しているハッカソンマンガ版「エンジニアでも恋がしたい!」〜転職初日にぶつかった女の子が同僚だった件〜」にチャレンジしてみました。これで100点を出すために必要だった「累積和」という考え方について今日は紹介します。


累積和

ある配列の全部足していってできる配列を「累積和」といいます。
例えば、

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

という配列の累積和は

[1, 1+2, 1+2+3, 1+2+3+4, …] →
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

になります

これが何がすごいかというと、ある配列の累積和を出しておくと、
その配列の部分配列の合計をたった1回の引き算で求めることができます。

例えば、
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
の一部の
[3, 4, 5, 6, 7, 8, 9](合計:42)
の合計は
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

9番目(45)から2番目(2)を引くことで求められるわけです。

つまりこんな式が成り立ちます。

a : ある配列
b : その累積和
s : aの部分配列の開始位置
l : aの部分配列の長さ

result = b[s + l – 1] – b[s – 1]

この公式をさっき例に当てはめてみると

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
s = 3
l = 7

b[3 + 7 – 1番目] – b[3 – 1番目]
b[9番目] – b[2番目]
45 – 3 = 42

部分配列の総和を何回も計算しないといけない場合などは、一度こうして元の配列の累積和を出しておくと楽に計算できます。


最後に

いつもはスルーしてたハッカソンだったのですが、今回は正解すると続きのストーリーが読めるというものだったので気になってやってみました。
下手に景品で釣るよりもこういうものの方がモチベーションが上がるのかもしれません。
うまく考えたなぁと思います。

最初、力任せに計算するプログラム書いたら60点でした。
そしたらこの累積和という考え方がヒントとして提示されていて、ググってなんと理解したかんじです。
アルゴリズムは普段あんまり考えないので勉強になりました。

ちなみに結果はRubyでこんなかんじです。
もっと早くできるかも。

プログラマーの方は
マンガ版「エンジニアでも恋がしたい!」〜転職初日にぶつかった女の子が同僚だった件〜
にチャレンジしてみてください!

ではでは。

このブログをRSS登録する! この記事をはてブする!

Comment

Zenback

Categories

  • Lifehack (57)
  • Web (140)
  • まとめ (172)
  • コンピュータ (132)
  • 仕事 (10)
  • 趣味 (104)
  • 雑記 (88)