Hatena::Grouptopcoder

TopCoder2D

 | 

2012-07-09

TopCoder SRM 549 Div1 参加記

| 00:27

きゅうりさんの帽子が出てきました.

結果

Rating

  • 1407 -> 1448

Score

  • Easy : 129.82 pt
  • Med : Unopened
  • Hard : Unopened
  • Challenge : +0/-0

Easy

  • 概要
    • 次の条件を満たす円錐A, Bを使って, 魔法使いの帽子を作ることができます.
      • Aの円錐をBの円錐の上にかぶせます.
      • このとき, Aの円錐の頂点は, Bの円錐の頂点より上側にないといけません.
      • また, Aの円錐の頂点とBの円錐の頂点が重なるのも許しません.
      • AをBにかぶせたとき, Bの円錐のどこか一部が見えていなければいけません.(完全にAがBにかぶさってはいけない)
    • 帽子の上側となる円錐の候補がN個. 帽子の下側となる円錐の候補がM個与えられます.
      • 各円錐は, 円錐の高さと, 円錐の半径が与えられる.
      • 以下の例は, 帽子が作れない例と作れる例です.

f:id:Respect2D:20120710002251j:image:w400

    • このとき, 最大でいくつの帽子を作ることができるでしょう.

  • 解法
    • 各円錐をグラフのノードとみなします.
    • 上側の円錐のノードと, 下側の円錐のノードとで, 帽子にできるペアをエッジでつなぎます.
    • あとは, このグラフについて, 二部グラフの最大マッチング問題を解けばいいです.
    • グラフはこんな感じになりますね↓

f:id:Respect2D:20120710002406p:image:w400

Med

  • 開けずに帰りました

My Comment

反省点

  • 英語読むの遅いです.
  • アジア地区もあるので, 英語の勉強しましょう.

よかった点

  • 貪欲をやらずに, 確実性のある二部マッチングで解いていたのはよかったでしょう.
  • でも, 貪欲解法思い付けた方がいいですね.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/Respect2D/20120709
 |