第138回【Python】累積和、区間和

現在取り組んでいるのは、paiza ラーニング問題集「クエリメニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 138 回目です。

相変わらず昆布茶を飲み続けています。毎朝 1 杯の昆布茶。飲み続けているのに好きにはなれません。なかなか美味しいと思えない。それでも、血圧が下がり、お腹の調子が整ったので、やめられないのです。

それでは、今日も頑張ってみようと思います。

累積和

長さ N の数列 A と、K 個の整数 Q_1 … Q_K が与えられるので、各整数 Q_i (1 ≦ i ≦ K) について A_1 … A_{Q_i} の和を求めてください。

N K
A_1
...
A_N
Q_1
...
Q_K

・1 行目では、配列 A の要素数 N と与えられる整数の数 K が与えられます。
・続く N 行では、配列 A の要素が A_1 から順に与えられます。
・続く K 行では、整数 Q_1 … Q_K が与えられます。

期待する出力

ans_1
...
ans_K

・i 行目に A_1 … A_{Q_i} の和 ans_i (1 ≦ i ≦ K)を出力してください。
・また、出力の末尾には改行を入れてください。

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N , K ≦ 100,000
・-100 ≦ A_i ≦ 100 (1 ≦ i ≦ N)
・1 ≦ Q_i ≦ N (1 ≦ i ≦ K)

入力例

3 1
69
12
28
3

出力例

109

累積和。知ってると知ってないとでは雲泥の差。

Python
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
ans = [0] + A[:]

for i in range(1,N+1):
    ans[i] += ans[i-1]
    
for _ in range(K):
    Q = int(input())
    print(ans[Q])
VBA
Sub query_primer__cumulative_sum()

    NK = Split(Cells(1, 1), " ")
    N = Val(NK(0))
    k = Val(NK(1))
    
    Dim A() As Long
    ReDim A(N) As Long
    
    For i = 1 To N
        v = Cells(i + 1, 1)
        A(i) = A(i - 1) + v
    Next
    
    For i = 1 To k
        q = Cells(i + N + 1, 1)
        Debug.Print A(q)
    Next
    
End Sub

いつもの如く、paiza の境界値付近のデータでテストした結果、約 70 秒。Debug.Print しなければ、約 0.5 秒で終わります。VBA もまだまだ頑張れる。

区間和

長さ N の数列 A と、K 個の区間 (l_1,r_1) … (l_K,r_K) が与えられるので、各区間についての A の区間和 A_{l_i} + … + A_{r_i} (1 ≦ i ≦ K) を求めてください。

N K
A_1
...
A_N
l_1 r_1
...
l_K r_K

・1 行目では、配列 A の要素数 N と与えられる整数の数 K が与えられます。
・続く N 行では、配列 A の要素が A_1 から順に与えられます。
・続く K 行では、和を求めるのに使う区間の値 l , r が与えられます。

期待する出力

ans_1
...
ans_K

・i 行目に A_{l_i} + … + A_{r_i} の和 ans_i (1 ≦ i ≦ K)を出力してください。
・また、出力の末尾には改行を入れてください。

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N , K ≦ 100,000
・-100 ≦ A_i ≦ 100 (1 ≦ i ≦ N)
・1 ≦ l_i ≦ r_i ≦ N (1 ≦ i ≦ K)

入力例

4 2
16
88
10
-65
2 4
1 2

出力例

33
104

区間和。こちらも知ってると知ってないとでは雲泥の差。

Python
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
ans = [0] + A[:]

for i in range(1,N+1):
    ans[i] += ans[i-1]
    
for _ in range(K):
    l,r = map(int,input().split())
    print(ans[r] - ans[l-1])
VBA
Sub query_primer__interval_sum()

    
    NK = Split(Cells(1, 1), " ")
    N = Val(NK(0))
    k = Val(NK(1))
    
    Dim A() As Long
    ReDim A(N) As Long
    
    For i = 1 To N
        v = Cells(i + 1, 1)
        A(i) = A(i - 1) + v
    Next
    
    For i = 1 To k
        lr = Split(Cells(i + N + 1, 1), " ")
        l = Val(lr(0))
        r = Val(lr(1))
        Debug.Print A(r) - A(l - 1)
    Next
    
End Sub

いつもの如く、paiza の境界値付近のデータでテストした結果、約 86 秒。Debug.Print しなければ、約 0.85 秒で終わります。ちゃんと、A(r) – A(l – 1) もやった状態です。VBA もまだまだ頑張れる。

最後に

区間和、累積和は、結構使う場面多いと思っています。個人的にですが。昔々に知識なく書いたコードがまったく実用に耐えず、いろいろと調べて知ったのが、区間和、累積和でした。ちょっと頭を柔らかくしたら思いつくことなのに、コードを書きながらではなかなかそこまで思いつけなかった苦い思い出でです。

いつも、VBA でもまだ出来ることはあるなぁと思いながら勉強しています。事務所内、うちのメンバーの間での業務効率化程度であれば、VBA でも十分です。もちろん、他にもいろいろと取り入れていますが、ちょっとしたこと、は VBA が一番楽だと思います。そのためにも、もっと勉強しなければ。アレ？ Python の勉強のためにやっているのではなかったかしら・・・。

引き続き、よろしくお願いいたします！

PythonPython,paiza,学習

Posted by LeoSaki