Rubyで二次元いもすを簡単に扱えるクラスを作ってみた

ほんっとうに久しぶりに精進しようと思ってABC434をAからDまでやったんですが、Dが結構いいところまで行ったのにいもす法の実装がすっぽ抜けてひどい有様だったのが悔しくて二次元いもすを管理するクラスを作りました。多分車輪の再発明だと思うのだけど、ブログに残しておかないとまた忘れると思う。「いもす法」って言葉すら思い出せなかったのが本当に悲しかったのでね…

一応ABC434-Dでこれを使って1350msくらいでACしているので大丈夫かなという気はします。とはいえ元のコードと比べると集計を個別にやってる分200msくらい性能劣化してるのでなんかうまい方法ないかなーっては思っている。多分問題によっては無視できないコストになると思うんだよな。

実際に使っている様子は提出コードをどうぞ。よく見たらコメントのxとyが逆なのよね、ちょっと恥ずかしい。 Submission #71635256 - Ｓｋｙ Inc, Programming Contest 2025 (AtCoder Beginner Contest 434)

class Imos2d
  def initialize(x, y)
    @x = x
    @y = y
    @matrix = Array.new(x + 2) { Array.new(y + 2, 0) }
  end

  def add(x_start, y_start, x_end, y_end, incr = 1)
    @matrix[x_start][y_start] += incr
    @matrix[x_start][y_end + 1] -= incr
    @matrix[x_end + 1][y_start] -= incr
    @matrix[x_end + 1][y_end + 1] += incr
  end

  def aggregate
    # y方向のいもす
    (@x + 2).times do |i|
      (1..(@y + 1)).each do |j|
        @matrix[i][j] += @matrix[i][j-1]
      end
    end

    # x方向のいもす
    (1..(@x + 1)).each do |i|
      (@y + 2).times do |j|
        @matrix[i][j] += @matrix[i-1][j]
      end
    end
  end

  def result(i, j)
    @matrix[i][j]
  end
end