# 最近解いたもの

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