トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginer Contest 002

[競技プログラミング]

AtCoder Beginer Contest 002

AtCoder Beginer Contest 002

けっこう易しい

  A - 正直者

lines = $stdin.read
array = lines.split("\n")
 
X = array[0].split(" ")[0].to_i
Y = array[0].split(" ")[1].to_i
 
if X > Y
  puts X
else
  puts Y
end

  B - 罠

lines = $stdin.read
array = lines.split("\n")
 
name = array[0]
 
puts name.gsub(/(a|i|u|e|o)/) {|c| ""}

  C - 直訴

lines = $stdin.read
array = lines.split("\n")
 
xa = array[0].split(" ")[0].to_f
ya = array[0].split(" ")[1].to_f
xb = array[0].split(" ")[2].to_f
yb = array[0].split(" ")[3].to_f
xc = array[0].split(" ")[4].to_f
yc = array[0].split(" ")[5].to_f
 
puts (xa*yb + xb*yc + xc*ya - ya*xb - yb*xc - yc*xa).abs/2

  D - 派閥

  • 何が間違っているのかなあ…
    • union-findを使ってみたのだが
  • 以下のような組み合わせのとき
5 3
1 2
2 3
3 4
  • {1, 2}, {2, 3}, {3, 4}は互いに一連のチェーンになってるから、合計人数の4が派閥になりそうだが
    • 問題文ではこれは2人ずつの派閥になるとのこと(全員が全員知り合いじゃないから)
    • となると、root()で木構造の頂点を取ってしまうとうまく派閥を作れないぞ…
lines = $stdin.read
array = lines.split("\n")
 
N = array[0].split(" ")[0].to_i
n = array[0].split(" ")[1].to_i
 
# idの数が確定
it = -1
id = Array.new(N){it+=1}
 
#
# union-findの準備
#
def root(i, id)
  while i != id[i] do
    i = id[i]
  end
  i
end
 
# find, check if p and q has the same root
def same?(p, q, id)
  root(p, id) == root(q, id)
end
 
# union, to merge components containing p and q
# set id of p's root to the id of q's root
def unite(p, q, id)
  i = root(p, id)
  j = root(q, id)
  id[i] = j
end
 
for i in 1..(array.length-1)
  x = array[i].split(" ")[0].to_i - 1
  y = array[i].split(" ")[1].to_i - 1
  #puts "#{x} #{y} #{id.to_s}"
  unite(x, y, id) unless same?(x, y, id)
end
 
habatsu = id.map do |e|
  root(e, id)
end
 
puts habatsu.uniq.map{|t| habatsu.count(t)}.max

解説

  D - 派閥(解き直し)

   「最大クリーク問題」と呼ばれる有名問題
   無向グラフにおいて、頂点の部分集合Cに対し、Cに含まれるあらゆる2つの頂点を繋ぐ辺が存在するようなCを、クリークと呼ぶ。
   
    • 今回はそのクリークのうち、最大のものを調べる
   
   NP困難の問題であることが知られている 
    ・・・が、こんな難しいことを知ってい る必要はありません!

どうやら力任せに解いてよいらしい。

…グエー、わからねー

人の解答を見てみる

  • Submission #1226221
    • N人の組み合わせをすべて羅列して、その後与えられたペアを数え上げている??わからん

Wikipedia

お名前: コメント: