れんしゅうちょう。

■ [FaceBookHackerCup]FaceBook Hacker Cup 2012 Qual 16:35

○|×|-

156位 16:49

まぁ撃沈ですね.しかし1問速解きで156位って割とあれな感じですね.速いのかよくわからんけど.

FHCでは,問題を解く順番がかなり重要っぽいので,最初に全ての問題を読んで概要を把握した.

Aが一番簡単そうでぱっと思い付いたので解いて提出.

Cが解けなさそうなので,2完だと時間勝負だなーと思い,Bを適当に書いたらsample通ったので提出.

Cはやっぱり解けず,Bも間違っていて死.

以下ソースとか.例によってテンプレ略な為見たければすこあぼーどへ.

Road Removal

重要な都市を含むループが出来ていて,何か取り除かなきゃいけないなら,重要な都市を含む辺を取り除いてもいいんじゃねえの?

なら,重要じゃない都市間のは全部OKって事でいいんじゃないの?

最後にクラスカル法みたいに閉路作らないように取っていけばいいんじゃないの?

という適当な考えの基に作った.

each_case do
  n,m,k = getia
  uf = UnionFind.new
  res = 0
  ab = []
  m.times do
    ab << getia.sort
  end
  ab.sort!.reverse!
  for i in 0...ab.size
    a,b = *ab[i]
    if a < k && uf.same?(a,b)
      res += 1
    else
      uf.join(a,b)
    end
  end
  res
end

Monopoly

名前がProjectEulerのあのめんどくさかったやつを彷彿とさせてアレだった.

問題文読んでいくと,UnionFindTreeやれみたいな感じであったので,Greedyでいいのかなーとか思いつつ親を選ぶ規則に修正を入れてみた.

Greedyではダメで,DPしなければならなかった模様.

確かにそうである.

ツイートする