Zenn
💨

いもす法をNumo::NArrayでやってみる

2021/07/05に公開
Ruby
競プロ
narray
tech

最近ruby-jpのslack[1]で紹介されていた、numo-narrayが面白そうだったので、 numo-narrayをつかっていもす法を利用する競プロの問題を解いてみました。

問題には競プロ典型 90 問の28日目: 028 - Cluttered Paper（★4）を使用しました。

準備

numo-narrayは ruby本体には付いてこないので別途gem installが必要です。

$ gem i numo-narray

実装

require 'numo/narray'

N = gets.to_i
M = 1001

field = Numo::Int32.zeros(M, M)
N.times do
  x1, y1, x2, y2 = gets.split.map(&:to_i)
  field[x1, y1] += 1
  field[x2, y1] -= 1
  field[x1, y2] -= 1
  field[x2, y2] += 1
end

1000.times do |i|
  field[i+1, true].inplace + field[i, true]
  field[true, i+1].inplace + field[true, i]
end

ans = Array.new(N+1, 0)
field.each{|e| ans[e] += 1}
(1..N).each do |i|
  puts ans[i]
end

解説

この問題は、平面上に紙を重ねっていって、最後に上から見たときの厚さ(n枚の紙が重なっていると厚さがn)毎の面積を答える問題になっています。

M = 1001
field = Numo::Int32.zeros(M, M)

これは、[M,M]の大きさを持ったすべての要素が0である行列を作ります。

x1, y1, x2, y2 = gets.split.map(&:to_i)
field[x1, y1] += 1
field[x2, y1] -= 1
field[x1, y2] -= 1
field[x2, y2] += 1

見てあきらかですが、
これは、行列の[x, y]の要素を更新しています。
2次元配列を使ったとき(field[x][y])と違って、field[x,y]のように行と列を同時に指定します。
コードの意味としては、紙を置いたときの左上の座標と右下の座標に1加え、右上と左下の座標から1減らす操作です。

1000.times do |i|
  field[i+1, true].inplace + field[i, true]
  field[true, i+1].inplace + field[true, i]
end

これは、行を上から下に列を左から右に累積和を求めています。
field[i, true]は i行目のビューを取得します。
同様に
field[true, i]は　i列目のビューを取得します。
ビューは元の行列に対しての参照になっているため、中身の要素は元の行列と同じものを指しており、ビューの要素を書き換えることで元の行列に対しての要素を書き換えます。
#inplaceには、レシーバーに対しての破壊的な変更を行う意味があり、直接レシーバーの要素を書き換えます。
ここでは、 i行目をi+1行目に足すという処理になります。
#inplaceを使わずに、

field[i+1, true] = field[i+1, true] + field[i, true]

のように書くこともできますが、新しいオブジェクトが生成されることでメモリを消費するため、今回は破壊的に変更を加えるようにしました。

ans = Array.new(N+1, 0)
field.each{|e| ans[e] += 1}
(1..N).each do |i|
  puts ans[i]
end


ここまでの処理で、フィールド上に紙の厚さに対応した要素が面積1につき1個できているので、各厚みを数えます。

field.eachは行列の各要素をイテレートするので、要素毎に計数用のans配列を+1し、最後に1~Nまでの厚さ毎の面積を出力して解答となります。

脚注

  1. https://ruby-jp.slack.com/archives/CM3BCS68M ↩︎

Discussion