# 最近解いたもの
2020/11/24
# AtCoder Beginner Contest 048
URL: https://atcoder.jp/contests/abc048 (opens new window)
# C
n,x = gets.chomp.split.map(&:to_i)
arr = [0] + gets.chomp.split.map(&:to_i)
count = 0
1.upto(n) do |i|
if arr[i-1] + arr[i] > x
# a[i-1] + a[i] = xとなるようにa[i]を減らす
tmp = x - arr[i - 1]
count += arr[i] - tmp
arr[i] = x - arr[i - 1]
end
end
puts count
2020/11/24
# AtCoder Beginner Contest 112
URL: https://atcoder.jp/contests/abc112 (opens new window)
# C
n = gets.chomp.to_i
# 全部高度が0となることは無いはず
arr = n.times.map{gets.chomp.split.map(&:to_i)}.sort_by{|x, y, h| -h}
0.upto(100) do |cx|
0.upto(100) do |cy|
# 中心座標をcx, cyと仮定するとその時の中心の高さを仮定することができる
x, y, max_h = arr[0]
h = max_h + (x - cx).abs + (y - cy).abs
# 他の座標で矛盾が無いことを示す
flag = true
1.upto(n-1) do |i|
x2, y2, h2 = arr[i]
if h2 != [h - (x2 - cx).abs - (y2 - cy).abs, 0].max
# 矛盾があれば飛ばす
flag = false
break
end
end
if flag
puts [cx, cy, h].join(" ")
exit
end
end
end
# D
n,m = gets.chomp.split(" ").map(&:to_i)
# 最大公約数をmax_mとすると a_1, a_2, ..., a_n はすべてmax_mで割り切れるので
# m = a_1 + a_2 + ... + a_n もmax_mで割り切れる
# 最大10^9ループ
(m / n).downto(1) do |i|
if m % i == 0
puts i
exit
end
end
2020/11/23
# AtCoder Beginner Contest 124
URL: https://atcoder.jp/contests/abc124 (opens new window)
# D
1010101があったとして2回反転できるとする。このとき両端の0を反転して1110111とするよりも, 1を無視して隣同士になっている0を反転して1111101とした方が良い。
1..10..01..1
n,k = gets.chomp.split.map(&:to_i)
s = gets.chomp
# 1の始点のindexを集めた配列(ただしsの左端が0の場合は便宜上このindexも含める)
one_start = []
# 1の終点のindexを集めた配列(ただしsの右端が0の場合は便宜上このindexも含める)
one_end = []
prev = ""
one_start << 0
s.each_char.with_index do |c, i|
if c == "0"
# "1" -> "0"
if prev == "1"
one_end << i - 1
end
else
# "0" -> "1"
if prev == "0"
one_start << i
end
end
prev = c
end
one_end << n-1
# 余計なindexが入っているので削除
one_start.pop if s[-1] == "1"
one_end.shift if s[0] == "1"
if one_start.length <= k
puts n
exit
end
max = 0
0.upto(one_start.length - k) do |i|
count = one_end[i + k - 1] - one_start[i] + 1
max = count if count > max
end
puts max