AtCoder Beginner Contest 002
www.slideshare.net
A - 正直者
nums = gets.split.map(&:to_i)
puts nums.max
B - 罠
str = gets.chomp puts str.gsub(/[aiueo]/, '')
C - 直訴
xa, ya, xb, yb, xc, yc = gets.split.map(&:to_i) puts ((xb - xa) * (yc - ya) - (yb - ya) * (xc - xa)).abs / 2.0
解説にあるように、符号付面積の公式を使う。
(0, 0), (a, b), (c, d)の3点が与えられたとき、求める面積Sは、となる。
(0, 0)に座標点がない場合でも、1点を(0, 0)と考えて残りの2点を平行移動して考えればよい。
(a, b), (c, d), (e, f)であれば、座標点を(0, 0), (c-a, d-b), (e-a, f-b)と設定する。
- 上記の公式を適用するなら、変数名はa, b, c, d, e, fを割り当てた方がわかりやすい
- ヘロンの公式を使う方法もあったか
D - 派閥
n, m = gets.split.map(&:to_i) if m.zero? puts 1 exit end relations = [] m.times { relations << gets.split.map(&:to_i) } n.downto(2) do |i| [*1..n].combination(i).each do |c| if c.combination(2).all? { |pair| relations.include? pair } puts i exit end end end
まず、M個の人間関係(知り合い関係)を全て配列に格納する。
N人いる場合、N, N-1, … , 2と多人数の派閥から検証していく。
派閥の成立条件は、派閥内の全ペアが知り合いであることなので、全ペアが配列に含まれているかを確かめればいい。
最大派閥の議員数を求めればよいので、多人数の派閥が見つかり次第、プログラムを終了する。
Range
をArray
に変換するには、Range#to_a
ではなく[*Range]
を使うほうが簡便- 最大クリーク問題