TopCoder2D

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個与えられます.
    • 各円錐は, 円錐の高さと, 円錐の半径が与えられる.
    • 以下の例は, 帽子が作れない例と作れる例です.

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

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

Med

• 開けずに帰りました

My Comment

反省点

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

よかった点

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