演習課題「いもす法の実装」
整数n,qとq回整数l,r,xが与えられます。
0で初期化された要素数nの配列aに対し、各l,r,xについてa[l],a[l+1],...,a[r]にxを加算してください。
いもす法を用いてこれを処理し、最終的に得られる配列aを出力してください。
入力を受け取るコードと配列aの先頭n個の要素を出力する関数print_array(a,n)がすでに用意されているので、コードを書き足してプログラムを完成させてください。
期待する出力値
0 100 110 111 100 0
※有料会員になるとこの動画をご利用いただけます
詳しい説明を読む
＃06:いもす法
このチャプターでは、いもす法と、先頭0個の和を考慮しない累積和について学習します。
いもす法-いもす研(imos laboratory)
https://imoz.jp/algorithms/imos_method.html
def print_array(a, n):
print(*a[:n])
n, l, r, x = map(int, input().split())
# 配列(リスト)aをサイズn+1で用意
a = [0] * (n+1)
# a[l]にxを、a[r+1]に-xを加算
a[l] += x
a[r+1] -= x
# iを1からn-1まで繰り返す
for i in range(1, n):
# a[i]にa[i-1]を加算
a[i] += a[i-1]
# aの先頭n要素を出力
print_array(a, n)
5 1 3 7
ログインすると採点できます
コードの実行