# 最近解いたもの

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

2020/11/23

# AtCoder Beginner Contest 108

URL: https://atcoder.jp/contests/abc108 (opens new window)

# D

h,w = gets.chomp.split.map(&:to_i)
arr = h.times.map{gets.chomp.split(" ").map(&:to_i)}

# 一筆書きで左上からジグザグに進めていく
# すなわち
# arr[0][0] -> arr[0][1] -> ... arr[0][w-1] ->
# arr[1][w-1] -> arr[1][w-2] -> ... arr[1][0] ->
# arr[2][0] -> arr[2][1] -> ... arr[2][w-1] ->
# ...
# コインの個数が偶数ならスキップ, 奇数なら次のマスに移すという操作を繰り返す

n = 0
result = []
h.times do |hi|
  w.times do |j|
    if hi % 2 == 0
      wi = j
      # 偶数行なら右または下に進める(基本は右, 右に進めなくなったら下)
      if wi < w - 1
        next_hi = hi
        next_wi = wi + 1
      elsif hi < h - 1
        next_hi = hi + 1
        next_wi = wi
      else
        next
      end
    else
      wi = w - 1 - j
      # 奇数行なら左または下に進める(基本は左, 右に進めなくなったら下)
      if wi > 0
        next_hi = hi
        next_wi = wi - 1
      elsif hi < h - 1
        next_hi = hi + 1
        next_wi = wi
      else
        next
      end
    end
    # コインが偶数ならスキップ
    next if arr[hi][wi] % 2 == 0
    # コインの移動
    arr[hi][wi] -= 1
    arr[next_hi][next_wi] += 1
    n += 1
    result << [hi, wi, next_hi, next_wi].map{|x| x+=1 }.join(" ")
  end
end
puts n
result.each do |row|
  puts row
end