AtCoder Beginner Contest 002

abc002.contest.atcoder.jp

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は、 S = \frac{|ad - bc|}{2}となる。
(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と多人数の派閥から検証していく。
派閥の成立条件は、派閥内の全ペアが知り合いであることなので、全ペアが配列に含まれているかを確かめればいい。
最大派閥の議員数を求めればよいので、多人数の派閥が見つかり次第、プログラムを終了する。

  • RangeArrayに変換するには、Range#to_aではなく[*Range]を使うほうが簡便
  • 最大クリーク問題

【参照】Rubyでの順列、組み合わせ。 - simanのブログ