🍡

[鉄則B06] Lottery

2024/04/20に公開

Ruby

累積和の応用問題。

問題を要約する

0 1 がランダムに並んでいる
L..R の範囲で 0 1 のどちらが多いか？

解法

0 1 を -1 1 に置き換えるとシンプルな累積和問題に合流するので、

A = [0, 1, 1, 0, 1, 0, 0]               # => [0, 1, 1, 0, 1, 0, 0]
A = A.collect { |e| e.zero? ? -1 : 1 }  # => [-1, 1, 1, -1, 1, -1, -1]

同じように進めていく。

S = A.each_with_object([0]) { |e, m| m << m.last + e }  # => [0, -1, 0, 1, 0, 1, 0, -1]
l, r = 1, 4
ans = S[r + 1] - S[l]                                   # => 2

最後に正負零に応じた文字列を表示する。

ans.positive?  # => true
ans.negative?  # => false
ans.zero?      # => false

解説の模範解答とは異なるが、これがもっとも簡単に思える。

実装 (AC)

234 ms

N = gets.to_i
A = gets.split.collect(&:to_i)                          # => [0, 1, 1, 0, 1, 0, 0]
Q = gets.to_i
LR = Q.times.collect { gets.split.collect(&:to_i).collect(&:pred) }
A.collect! { |e| e.zero? ? -1 : 1 }                     # => [-1, 1, 1, -1, 1, -1, -1]
S = A.each_with_object([0]) { |e, m| m << m.last + e }  # => [0, -1, 0, 1, 0, 1, 0, -1]
ans = LR.collect { |l, r| S[r + 1] - S[l]  }            # => [2, 0, -1]
ans = ans.collect { |e| {-1 => :lose, 0 => :draw, 1 => :win}[e <=> 0] }
ans                                                     # => [:win, :draw, :lose]
puts ans

解説の模範解答風 (AC)

241 ms

N = gets.to_i
A = gets.split.collect(&:to_i)  # => [0, 1, 1, 0, 1, 0, 0]
Q = gets.to_i
LR = Q.times.collect { gets.split.collect(&:to_i).collect(&:pred) }
S = A.each_with_object([[0], [0]]) { |e, m|
  m[0] << (e == 0 ? m[0].last + 1 : m[0].last)
  m[1] << (e == 1 ? m[1].last + 1 : m[1].last)
}
S[0]                            # => [0, 1, 1, 1, 2, 2, 3, 4]
S[1]                            # => [0, 0, 1, 2, 2, 3, 3, 3]
ans = LR.collect do |l, r|
  v0 = S[0][r + 1] - S[0][l]    # => 1, 3, 2
  v1 = S[1][r + 1] - S[1][l]    # => 3, 3, 1
  v1 - v0                       # => 2, 0, -1
end
ans = ans.collect { |e| {-1 => :lose, 0 => :draw, 1 => :win}[e <=> 0] }
ans                             # => [:win, :draw, :lose]
puts ans

解説の模範解答の考え方

解説の方法は、

0 と 1 に対応する累積和配列を別々に作る
累積和を作る過程で前の値を引き継ぐ場合もある
和ではなく +1 とする

のように行うので動的計画法に似てややこしい。とはいえ、別々にすることで、

0 だけを対象にした区間の合計を求めよ
1 だけを対象にした区間の合計を求めよ

とされたときも答えを出せる。

問題を要約する

解法

実装 (AC)

解説の模範解答風 (AC)

解説の模範解答の考え方

Discussion