アルゴリズムでよく使う手法まとめ

paizaでアルゴリズムの練習問題でよく使い、よくつまずくポイントを残します。

向きについて

マスを進んでいく問題で向きを変えながら一マスずつ進む問題での向き判定

# 左から上、右、下、左
move = [[-1, 0], [0, 1], [1, 0], [0, -1]]

# 向き
now = 0

# 初期位置
y, x = [3, 3]

# 向きによってy, xを変える
# 向きの値を4で割り、その値によってmoveに入っている変化する値を取得できる。
ny = y + move[now % 4][0]
nx = x + move[now % 4][1]

# 方向変換がある場合、値を1増減することで４で割って出るあまりの値を変える。
if d == 'L'
  now -= 1
else
  now += 1
end

# 枠が指定されている場合はみ出さないように判定する
h = 10
w = 10
0 <= ny && ny <= h - 1 && 0 <= nx && nx <= w - 1

累積和

配列の任意の合計を求める

array = [1, 2, 3, 4, 5, 6]
s = [0]
array.each do |i|
  s << s[-1] + i
end 
#[0, 1, 3, 6, 10, 15, 21]

いもす法
一つ前の要素との比較でどれだけ増減しているのかを記録した配列を作成し、その配列を使い累積和を作成する。
例題
店に0〜１０時の間の１時間ごとに何人の客がいたかを調べる
客ごとの在席時間は2~5, 3~4, 8~10とする。

# 店の営業時間
n = 10

# 客の在席時間
people = [[2, 5], [3, 4], [7, 9]]

# 一時間前との比較
s = Array.new(n + 1, 0)
people.each do |e, l|
  s[e] += 1
  s[l + 1] -= 1
end

# s == [0, 0, 1, 1, 0, -1, -1, 1, 0, 0, -1]

times = Array.new(n + 1, 0)
times[0] = s[0]
1.upto(n) do |i|
  times[i] = times[i - 1] + s[i]
end

# times == [0, 0, 1, 2, 2, 1, 0, 1, 1, 1, 0]

二次元の累積和

縦横の累積和

s = Array.new(h + 1) { Array.new(w + 1, 0) }
0.upto(h - 1) do |y|
  0.upto(w - 1) do |x|
    # ゼータ変換
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

任意の長方形の領域の総和

section.each do |a, b, c, d|
  puts s[d][c] + s[b - 1][a - 1] - s[d][a - 1] - s[b - 1][c]
end