AtCoder ARC #080 / ABC #069

arc080-a.rb

# K-City
n, m = gets.chomp.split(" ").map(&:to_i)
puts (n - 1) * (m - 1)

arc080-b.rb

# i18n
s = gets.chomp
n = s.length
puts "#{s[0]}#{n-2}#{s[-1]}"

arc080-c.rb

# 4-adjacent
n = gets.chomp.to_i
arr = gets.chomp.split(" ").map(&:to_i)

mod4 = Array.new(3, 0)

arr.each do |a|
  cnt = 0
  while true
    break if cnt == 2
    if a.even? then
      cnt += 1
      a /= 2
    else
      break
    end
  end
  mod4[cnt] += 1
end

x = [mod4[2], mod4[0]].min
mod4[0] -= x
mod4[2] -= x
if mod4[0] > 1  then
  puts "No"
elsif mod4[0] == 1
  if mod4[1] == 0 then
    puts "Yes"
  else 
    puts "No"
  end 
else
  puts "Yes"
end

arc080-d.rb

# Grid Coloring
h, w = gets.chomp.split(" ").map(&:to_i)
n = gets.chomp.to_i
arr = gets.chomp.split(" ").map(&:to_i)

x = []
arr.each_with_index do |a, i|
  x += Array.new(a, i+1)
end
i = 1
x.each_slice(w) do |a|
  if i.even?
    puts a.reverse.join(" ")
  else
    puts a.join(" ")
  end
  i += 1
end

arc080-e.py

# TLE
import heapq
MAX_N = 1 << 17
INT_MAX = 2**31 - 1
 
class SegmentTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.dat = [INT_MAX] * (2 * self.n - 1)
 
    def update(self, k, a):
        k += (self.n - 1)
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            if self.dat[k * 2 + 1] < self.dat[k * 2 + 2]:
                self.dat[k] = self.dat[k * 2 + 1]
            else:
                self.dat[k] = self.dat[k * 2 + 2]
            # self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])
 
    def query(self, a, b, k, l, r):
        if (r <= a) or (b <= l):
            return INT_MAX
        if (a <= l) and (r <= b):
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
            if vl < vr:
                return vl
            else:
                return vr
            # return min(vl, vr)
 
def wrap_query(type, a, b, k, l):
    if type == "even":
        if a % 2 == 0:
            ret = st_even.query(a, b, k, l, st_even.n)
        else:
            ret = st_odd.query(a, b, k, l, st_odd.n)
    else:
        if a % 2 == 0:
            ret = st_odd.query(a, b, k, l, st_odd.n)
        else:
            ret = st_even.query(a, b, k, l, st_even.n)
    return ret
 
class Item():
    def __init__(self, mini, left, right):
        self.mini = mini
        self.left = left
        self.right = right
 
if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split(" ")))
    st_even = SegmentTree(n)
    st_odd = SegmentTree(n)
    h = dict()
    for i in range(n):
        h[arr[i]] = i
        if i % 2 == 0:
            st_even.update(i, arr[i])
        else:
            st_odd.update(i, arr[i])
    q = [None] * n
    hq = []
    x = wrap_query("even", 0, n, 0, 0)
    heapq.heappush(hq, (x, Item(h[x], 0, n)))
    ii = 0
    while len(hq) != 0:
        q0, item = heapq.heappop(hq)
        l = item.left
        r = item.right
        i = item.mini
        q[ii] = q0
        ii += 1
        # q.append(q0)
        q1 = wrap_query("odd", i, r, 0, 0)
        j = h[q1]
        q[ii] = q1
        ii += 1
        # q.append(q1)
        if i - l > 1:
            x0 = wrap_query("even", l, i, 0, 0)
            heapq.heappush(hq, (x0, Item(h[x0], l, i)))
        if j - (i+1) > 1:
            x1 = wrap_query("even", i+1, j, 0, 0)
            heapq.heappush(hq, (x1, Item(h[x1], i+1, j)))
        if r - (j + 1) > 1:
            x2 = wrap_query("even", j+1, r, 0, 0)
            heapq.heappush(hq, (x2, Item(h[x2], j+1, r)))
    print(*q, sep=" ")