オフラインリアルタイムどう書く E25 の解答

qiita.com

オンライン参加で解けました。17:02なので45分くらいでしょうか。

方針としては、たかだか200x200マス = 40000通りなので、スタート地点以外の1点を選んでベクトル作ってベクトル回して伸ばして座標が盤面内にあるかどうかを確認するので間に合いそうです。おわり。

というのを問題をみて3分くらいで決めたんだけど、回転下手なのと盤面の境界条件を間違えるといういつもので苦戦してました。 というわけでコード。割と汚めです。

class Solver
  def initialize
  end

  def solve(input)
    w, h, str = input.split(',', 3)
    @w = w.to_i
    @h = h.to_i
    x, y = str.scan(/\d+/).map(&:to_i)
    answer = {}
    s = [x, y]

    @w.times do |sx|
      @h.times do |sy|
        v = [sx - x, sy - y]
        ps = points(s, v)
        if ps.all? { |p| valid?(p) }
          l = len_of(v)
          answer[l] ||= []
          answer[l] << ps
        end
      end
    end

    m = answer.keys.max
    if answer[m].size == 1 && m != 0
      answer[m].first.map { |p| "(#{p.first},#{p.last})" }.join(",")
    else
      '-'
    end
  end

  def len_of(v)
    Math.sqrt(v.first**2 + v.last**2)
  end

  def valid?(p)
    (0...@w).include?(p.first) && (0...@h).include?(p.last)
  end

  def points(s, v)
    sx, sy = s
    a, b = v
    p1 = [sx + a, sy + b]
    p2 = [p1.first - b, p1.last + a]
    p3 = [p2.first - 2*a, p2.last - 2*b]
    [p1, p2, p3]
  end
end

リファクタリングしたのでこっちのがみやすいかも。あとサイズ小さいやつとか見る意味ないじゃんって気づいたので途中で next いれるようにしました(max_l あたり)

class Solver
  Pair = Struct.new(:x, :y) do
    def add(other)
      Pair.new(x + other.x, y + other.y)
    end

    def sub(other)
      Pair.new(x - other.x, y - other.y)
    end

    def multi(s)
      Pair.new(x * s, y * s)
    end

    def rotate270
      Pair.new(-y, x)
    end

    def to_s
      "(#{x},#{y})"
    end

    def size
      Math.sqrt(x**2 + y**2)
    end
  end

  def solve(input)
    w, h, str = input.split(',', 3)
    @w = w.to_i
    @h = h.to_i
    x, y = str.scan(/\d+/).map(&:to_i)
    answer = {}
    s = Pair.new(x, y)
    max_l = 0

    @w.times do |sx|
      @h.times do |sy|
        v = Pair.new(sx, sy).sub(s)
        next if v.size < max_l
        ps = points(s, v)
        if ps.all? { |p| valid?(p) }
          l = v.size
          answer[l] ||= []
          answer[l] << ps
          max_l = l if l > max_l
        end
      end
    end

    m = answer.keys.max
    if answer[m].size == 1 && m != 0
      answer[m].first.map(&:to_s).join(",")
    else
      '-'
    end
  end

  def valid?(p)
    (0...@w).include?(p.x) && (0...@h).include?(p.y)
  end

  def points(s, v)
    p1 = s.add(v)
    p2 = p1.add(v.rotate270)
    p3 = p2.sub(v.multi(2))
    [p1, p2, p3]
  end
end