[解決済み] マトリックスサムネーションチャレンジ

質問内容

以下のアルゴリズムは、「下の行列」を「後の行列」に変換するために使用される。このとき、quot;after行列が与えられたら、quot;before行列を求めよ。

各 after(x,y) に対してアルゴリズムを実行し、その値を決定します。afterが与えられたら、beforeの元の値を求める

例

after = [[2,5],[7,17]] とする。

afterの値をbeforeから計算する

after[0][0] = before[0][0] = 2

after[0][1] = before[0][0] + before[0][1] = 2 + 3 = 5

after[1][0] = before[0][0] + before[1][0] = 2 + 5 = 7

after[1][1] = before[0][0] + before[0][1] + before[1][0] + before[1][1] = 2 + 3 + 5 + 7 =  17

行列が次のパラメータを持つ前に、関数 find before matrix を完成させる。 after[n][m]: n x m の整数の配列

を返します。 int[n][m] 前行列を表す n x m の整数の配列

制約条件

もう1つの入力例

これまでに試したこと

n = gets.to_i
m = gets.to_i

arr = Array.new(n){Array.new(m,0)}
sum = 0
arr_last = 0
arr_first = 0
len = 0
a.each_with_index do |d, outer_index|
  len = d.length - 1
  d.each_with_index do |b, index|
    arr_sum = d[0..index].sum
    if index > 0
      arr[outer_index][index] = sum + arr_sum
    else
      arr[outer_index][index] = arr_first + b
    end
    arr_first += b if index == 0
    arr_last = arr_sum if index == len 
  end
  sum += arr_last
end

print arr

しかし、いくつかのテストケースでは制限時間内に実行されず、いくつかのテストケースでは間違った答えが返ってきました。

解決方法は？

Afterグリッドの各値は、その前の値と、その左または上にあるすべての前の値の合計である。図では

• B は、赤色部分のBefore値の総和です。
• Y は、緑と赤の領域におけるすべてのBefore値の合計である。
• X は、青と赤の領域におけるすべてのBefore値の合計、および
• A は、紫、青、緑、赤の各領域のBefore値の合計である。

以来 X と Y で重なる。 B を追加する。 X と Y を持つことになります。 B が2回カウントされます。ですから、もし A を引きます。 X と Y を追加し、さらに B (2倍を打ち消すため)、Beforeの値を得る。 A というように A' = A - X - Y + B .

それがわかったので、コードはとてもわかりやすくなっています。

def before(after)
  before = []
  after.each_with_index do |row,j|
    before[j] = []
    row.each_with_index do |v,i|
      up = j <= 0 ? 0 : after[j-1][i]
      left = i <= 0 ? 0 : after[j][i-1]
      up_left = i <= 0 || j <= 0 ? 0 : after[j-1][i-1]
      before[j][i] = v - up - left + up_left
    end
  end
  before
end