2次元累積和をまなぶ
AtCoderの勉強でかねてより累積和の勉強をすすめていた。一段落したので記録しておく。
参考にした記事はこちらです。
1次元累積和はけっこう簡単で、この記事を読めばだいたい理解できる。コードも1次元の配列を使うだけなのでわりとすんなりかける。
書き方によって配列要素のインデックスを +1
するのか -1
するのか気をつける程度でなので、1つの問題を解くのにもあまり時間がかからない。
例題をいくつか解けば手に馴染んでくる。
しかし、2次元累積和になるとちょっと話が変わってくる。
ゼータ変換のほうがわかりやすい?
2次元累積和を素直に考えると、以下の図のように考えて、このような式で求めていく
s[x+1][y+1] = s[x][y+1] + s[x+1][y] − s[x][y] + a[x][y]
でもこの方法は、ちょっと頭を使わないといけなくてx
y
の動きとs[x+1][y+1]
の結果がなんかしっくりこない。
視覚的に動きを見えるようにしたら理解できた。可視化は理解の手助けになる。コードはRubyで書いた。
H, W = 4, 5 A = [ [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1] ] s = Array.new(H+1){ Array.new(W+1) { 0 } } print "\e[H\e[2J" (0...H).each do |i| (0...W).each do |j| s[i+1][j+1] = A[i][j] + s[i+1][j] + s[i][j+1] - s[i][j] puts "(%s, %s)" % [i, j] pp s sleep 1 print "\e[H\e[2J" end end pp s # 累積和の配列 s # => [ # [0, 0, 0, 0, 0, 0], # [0, 1, 2, 3, 4, 5], # [0, 2, 4, 6, 8, 10], # [0, 3, 6, 9, 12, 15], # [0, 4, 8, 12, 16, 20] # ]
一方ゼータ変換で累積和を求める方は直観的に理解しやすく、コードも書きやすかった。
ゼータ変換はこちらで詳しく解説されています。
コードはこんな感じ
H, W = 4, 5 A = [ [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1] ] s = Array.new(H){ Array.new(W) { 0 } } (0...H).each do |i| (0...W).each do |j| if i == 0 s[i][j] = A[i][j] else s[i][j] = s[i-1][j] + A[i][j] end end end (0...H).each do |i| (0...W).each do |j| if j == 0 s[i][j] += 0 else s[i][j] += s[i][j-1] end end end pp s # 累積和の配列 s # => [ # [1, 2, 3, 4, 5], # [2, 4, 6, 8, 10], # [3, 6, 9, 12, 15], # [4, 8, 12, 16, 20] # ]
さて、累積和の計算結果は同じになったものの、配列の構造は若干異なっている。
その結果、ゼータ変換で作成された配列を実際の計算で使う場合は、配列インデックスが -1
になる場合や、始点と終点が重なる場合の計算など、あとから気を使う場面が増えてしまった。
どちらの方法が良いのか。
例題をどちらの方法でも説いたけど、前者のほうがコードの量も短くてすんだし、速度も出た。いろいろ考えてコードを書いてみた結果、理解が深まったのでこれからも前者のやり方をすると思う。
例題はABC005のD - おいしいたこ焼きの焼き方という問題。処理時間も前者のほうが 100ms 速かった。もちろんゼータ変換でも、もっと良い書き方があるはずだけど。
蟻本の目次には累積和がなくて、最近は離れてしまっていたけど、また改めて進めていきたい。
プロコンやりたい人は
はんなりPythonの勉強会でAtCoderに取り組む会をやっているので興味のある人は参加してみてください。参加者も徐々に増えつつあります。