レートは下げなかったが全完するべき回だった。

結果

A, B, Dの3完。Cが解けなかった。
C > Dの難易度だったように感じたが、Cの左右から累積和(累積GCD)をとる発想は典型らしい。

コンテスト後にRubyで解き直したコードを載せる。

A - Biscuit Generator

a, b, t = gets.strip.split.map(&:to_i)
puts b * (t / a)

B - Resale

価値 - コストがプラスになっているものだけ選べばいい。

n = gets.to_i
vs = gets.split.map(&:to_i)
cs = gets.split.map(&:to_i)

puts (0..n - 1).map {|i| [vs[i] - cs[i], 0].max }.inject(:+)

C - GCD on Blackboard

コンテスト中にACできなかった。
左から累積GCDをとることは考えたが、$$i$$番目を取り除くとした時に、$$A1$$ .. $$A{i-1}$$と$$A{i+1}$$ .. $$AN$$の2つの区間に別れるが、 後ろの$$A{i+1}$$..$$AN$$の区間は$$A_i$$を含めたgcdになっているのでs[left] - s[right]みたいなことはできない。
ここでダメだなとなって累積GCDのことは考えるのをやめてしまった。
気づけば簡単で、左からだけじゃダメなら右からも累積GCDとればよい。

これが発想できなかったのが非常に残念。
解いたことある問題しか解けないマンじゃないか。

n = gets.to_i
a = gets.split.map(&:to_i)

left_gcd = Array.new(n + 1, 0)
right_gcd = Array.new(n + 1, 0)

(0..n - 1).each do |i|
    left_gcd[i + 1] = left_gcd[i].gcd(a[i])
end

(n - 1).downto(0) do |i|
    right_gcd[i] = right_gcd[i + 1].gcd(a[i])
end

ans = 0
(0..n - 1).each do |i|
    left = left_gcd[i]
    right = right_gcd[i + 1]
    ans = [ans, left.gcd(right)].max
end

puts ans

D - Flipping Signs

コンテスト中に考えたこと
先頭から2つずつみていって、数字の正負の並びに応じて以下の操作を行う。

• ++のとき => 何もしない
• +-のとき => 何もしない
• -+のとき => +-にする
• --のとき => ++にする

全てが+になっていれば単純に総和sumが求める答え。
-が残っていれば(ひとつしか残らない)、絶対値が一番小さいものminを-にして、sum - 2 * minが答え。
なぜ絶対値が一番小さいものを-にしていいかというと、 +-は-+にできて-+は+-にできるので、-の位置を自由に移動できるため。

よくよく考えると
先頭から2つずつみていく操作は完全に無駄で、数列中の負の整数が偶数個なのか奇数個なのかさえわかればいい。 数列中の-は自由に移動できるので、-が偶数個なら一箇所に集めることができて全て+にできる。 奇数個ならひとつ-が残り、それは絶対値が最も小さい数字を選ぶのが最適。

このことに気付ければもっと早く提出できていた…。

n = gets.to_i
as = gets.split.map(&:to_i)

count = as.count { |i| i < 0 }
to_abs = as.map { |e| e.abs }

if count.even?
    puts to_abs.reduce(:+)
else
    min = to_abs.min
    puts to_abs.reduce(:+) - min * 2
end