Zenn
📐

[ABC175 B] Making Triangle

2024/03/17に公開
Ruby
AtCoder
競プロ
三角形
tech

https://atcoder.jp/contests/abc175/tasks/abc175_b

三角形の条件を判定する問題。

三角形の条件の判定方法

方法1. 任意の2辺の長さの合計が残りの1辺の長さよりも大きいか？

a, b, c = edges  # => [5, 4, 3]
v = [
  a + b > c,
  b + c > a,
  c + a > b,
].all?
v                # => true

方法2. 最大の辺より残りの2辺の合計の方が大きいか？

a, b, c = edges.sort  # => [3, 4, 5]
a + b > c             # => true

方法3. 辺の合計が辺の最大×2より大きいか？

edges                      # => [5, 4, 3]
edges.sum > edges.max * 2  # => true

参考: https://www.youtube.com/watch?v=auQRcs5JMwE&t=358s

自力解答 (AC)

N = gets.to_i                   # => 5
L = gets.split.collect(&:to_i)  # => [4, 4, 9, 7, 5]
count = L.combination(3).count do |v|
  if v.uniq.size == v.size
    x, y, z = v.sort
    x + y > z
  end
end
p count                         # => 5

ソートしすぎで非効率だった。

解説の模範解答1 (AC)

N = gets.to_i                   # => 5
L = gets.split.collect(&:to_i)  # => [4, 4, 9, 7, 5]
L.sort!                         # => [4, 4, 5, 7, 9]
count = L.combination(3).count do |v|
  if v.uniq.size == v.size
    x, y, z = v
    x + y > z
  end
end
p count                         # => 5

ソートは全体に対して一度行なうだけでよかった。

解説の模範解答2 (AC)

N = gets.to_i                   # => 5
L = gets.split.collect(&:to_i)  # => [4, 4, 9, 7, 5]
count = L.combination(3).count do |v|
  if v.uniq.size == v.size
    v.sum > v.max * 2
  end
end
p count                         # => 5

三角形の条件判定を「辺の合計が辺の最大×2より大きい」とする方法でソートが不要になる。こんな公式初めて知った。

ソートを使わない別の方法 (AC)

N = gets.to_i                   # => 5
L = gets.split.collect(&:to_i)  # => [4, 4, 9, 7, 5]
count = L.combination(3).count do |v|
  if v.uniq.size == v.size
    a, b, c = v
    a + b > c && b + c > a && c + a > b
  end
end
p count                         # => 5

冗長だが3回判定すればソートが不要になる。

参考

Discussion