演習課題「二次元累積和を求める」
整数n,mとn×mの二次元配列aが与えられるので、二次元累積和を出力してください。
今回考える累積和は、先頭0個の和を考慮するものとします(各行・各列の先頭の値は0になります)。
入力を受け取るコードと出力用の関数print_2d_arrayがすでに用意されているので、コードを書き足してプログラムを完成させてください。
期待する出力値
0 0 0 0 0 0
0 1 3 6 10 15
0 3 8 15 24 35
0 6 15 27 42 60
0 10 24 42 64 90
0 15 35 60 90 125
演習課題「二次元累積和を求める(inclusive scan)」
整数n,mとn×mの二次元配列aが与えられるので、二次元累積和を出力してください。
今回考える累積和は、先頭0個の和を考慮しないものとします(各行・各列の先頭の値はaの同じ位置にある要素の値に等しくなります)。これについて詳しくはTipsを参考にしてください。
入力を受け取るコードと出力用の関数print_2d_arrayがすでに用意されているので、コードを書き足してプログラムを完成させてください。
期待する出力値
1 3 6 10 15
3 8 15 24 35
6 15 27 42 60
10 24 42 64 90
15 35 60 90 125
#05:二次元累積和
このチャプターでは、二次元累積和について学習します。
二次元累積和による範囲の和の求め方と同じように考えると、s[i+1][j]+s[i][j+1]-s[i][j]という値は、s[i+1][j+1]からa[i][j]の部分だけ取り除いた太いL字型の区間の和になっています。 よって、この値にa[i][j]を加算することでs[i+1][j+1]を正しく求めることができます。
要素数0個の和を考慮しない累積和の計算を行う場合は、iを0からn-1まで繰り返してs[0][i]=a[0][i],s[i][0]=a[i][0]としたのち、iを1からn-1まで,jを1からm-1まで繰り返してs[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]とすることで求めることができます。配列sのサイズはn×mになることに注意しましょう。
また、元の配列でそのまま計算する場合は、一次元の場合の先頭0個の和を考慮しない累積和の計算を各行に対して行ったのち、同じ計算を各列に対しても行うことで、二次元累積和を求めることができます。
具体的には、iを0からn-1まで、jを1からm-1まで繰り返してa[i][j]+=a[i][j-1]としたのち、jを0からm-1まで、iを1からn-1まで繰り返してa[i][j]+=a[i-1][j]とします。
n, m = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
a = [[int(x) for x in input().split()] for _ in range(n)]
# 累積和をとる二次元配列(リスト)sを0で初期化
s = [[0] * (m+1) for _ in range(n+1)]
# iが0からn-1まで、jが0からm-1までのループを回す
for i in range(n):
for j in range(m):
# s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j]+a[i][j]とする
s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + a[i][j]
# s[x2+1][y2+1]-s[x2+1][y1]-s[x1][y2+1]+s[x1][y1]を出力
print(s[x2+1][y2+1] - s[x2+1][y1] - s[x1][y2+1] + s[x1][y1])
3 3
0 0 2 2
8 0 0
0 1 0
0 0 3