第139回【Python】二次元累積和

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

はじめに

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

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

年間 5 日の有給休暇、消化できていますか？ LeoSaki（旦那）は、まったく取れていません。利用している勤怠システムに有給取得を促すアラートが出続けています。一方で、ほぼ全部の有給を消化する人もいるわけです。その人が休んだ分も対応しないといけないこともあり、不公平感がやるせない。

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

二次元累積和

H 行 W 列 の行列 A の y 行 x 列における累積和 S(y,x) を以下の数式・図の通り定義します。以後 A の y 行 x 列の要素を A[y][x] と表すことにします。

S(y,x) = A[1][1] + A[1][2] + … + A[1][x] + A[2][1] + … + A[2][x] + … + A[y][1] + … + A[y][x]

H 行 W 列 の二次元配列 A と、累積和を求めたい行・列番号についての情報が与えられるので、各ペアについて累積和を求めてください。
例として、入力例 1 の行列における累積和 S(2,2) は次のピンクの部分の和となり、S(2,2) = 12 となります。

H W N
A[1][1] ... A[1][W]
...
A[H][1] ... A[H][W]
y_1 x_1
...
y_N x_N

・1 行目では、配列 A の行数 H と列数 W , 与えられる整数のペアの個数 N が与えられます。
・続く H 行のうち i 行目では、行列 A の i 行の要素が半角スペース区切りで A[i][1] から順に与えられます。
・続く N 行では、累積和を求めるのに使う整数のペア y , x が N 個与えられます。

期待する出力

ans_1
...
ans_N

・i 行目に S(y_i , x_i) の値 ans_i (1 ≦ i ≦ N) を出力してください。
・また、出力の末尾には改行を入れてください。

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

・1 ≦ H , W ≦ 1,000
・1 ≦ N ≦ 100,000
・-100 ≦ A[i][j] ≦ 100 (1 ≦ i ≦ H , 1 ≦ j ≦ W)
・1 ≦ y_i ≦ H , 1 ≦ x_i ≦ W (1 ≦ i ≦ N)

入力例

3 3 3
1 2 3
4 5 6
7 8 9
1 1
2 2
3 3

出力例

1
12
45

回答を求めるための配列の作り方をどんな風にするか、がポイントになりそう。標準入力から受ける際にそのまま 0 の配列を作ってもいいと思っていたのだけれど、模範解答は別々に作っていたので真似てみました。

Python
H,W,N = map(int,input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]
ans = [[0] * (W+1) for _ in range(H+1)]

for i in range(1,H+1):
    ans[i] = [0] + A[i-1][:]
    for j in range(1,W+1):
        ans[i][j] += ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1]

for _ in range(N):
    y,x = map(int,input().split())
    print(ans[y][x])
VBA
Sub query_primer__two_dimensions_cumulative__sum()

    HWN = Split(Cells(1, 1), " ")
    h = Val(HWN(0))
    w = Val(HWN(1))
    N = Val(HWN(2))
    
    Dim A() As Long
    ReDim A(h, w)
    
    For i = 1 To h
        s = Split(Cells(i + 1, 1), " ")
        For j = 1 To w
            A(i, j) = s(j - 1)
        Next
    Next
    
    For i = 1 To h
        For j = 1 To w
            A(i, j) = A(i, j) + A(i - 1, j) + A(i, j - 1) - A(i - 1, j - 1)
        Next
    Next
    
    For i = 1 To N
        yx = Split(Cells(i + H + 1, 1), " ")
        y = Val(yx(0))
        x = Val(yx(1))
        Debug.Print A(y, x)
    Next

End Sub

いつもの如く、境界値データテストでは、約 79 秒。Debug.Print しなければ、0.9 秒。

最後に

二次元でもやることは同じ、と思いきや、共通部分を「引く」作業を忘れないように。これは、ご自身で図でも書いて確かめてみるとわかりやすいと思います。LeoSaki（旦那）も、最初の頃は手書きで書いていました。

VBA の方は、integer 型や long 型で初期化すると、0 が入るので、それを活用しています。配列に配列を足すくらいならまだしも、配列に 1 つ 0 を追加するのは大変な労力となってしまうので。

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

Pythonpaiza,学習,Python

Posted by LeoSaki