Snippets

cia_rana ◯はぴったり☓は無し

Created by cia_rana last modified
def parse_input(input)
  n, *maru_batsu = input.split
  [n.to_i, *maru_batsu.map{|e|e.split(?,).map{|e|[e[0].ord-65, e[1].ord-97]}}]
end

def initialize_map(points)
  map = Array.new(27){Array.new(27){0}}
  points.each{|x, y|
    map[y+1][x+1] = 1
  }
  (1..26).each{|y|
    (2..26).each{|x|
      map[y][x] += map[y][x-1]
    }
  }
  (2..26).each{|y|
    (1..26).each{|x|
      map[y][x] += map[y-1][x]
    }
  }
  map
end

def solve(input)
  n, maru_points, batsu_points = parse_input(input)
  
  maru_map = initialize_map(maru_points)
  batsu_map = initialize_map(batsu_points)
  
  # 探索範囲はo,xの4隅またはマップ端に隣接しているので、探索範囲を絞る
  xs, ys = (maru_points + batsu_points).transpose.map{|es|(es + es.map{|e|e+1} + [0, 26]).sort.uniq}
  
  max_area = -1
  (0..(ys.size-2)).each{|it|
    (0..(xs.size-2)).each{|jl|
      ((it + 1)..(ys.size - 1)).each{|ib|
        ((jl + 1)..(xs.size - 1)).each{|jr|
          t, l, b, r = ys[it], xs[jl], ys[ib], xs[jr]
          break if batsu_map[b][r] - batsu_map[b][l] - batsu_map[t][r] + batsu_map[t][l] > 0
          maru_num = maru_map[b][r] - maru_map[b][l] - maru_map[t][r] + maru_map[t][l]
          break if maru_num > n
          max_area = [max_area, (b - t) * (r - l)].max if maru_num == n
        }
      }
    }
  }
  
  max_area < 0 ? ?- : max_area
end

puts solve(gets)

Comments (0)

HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.