トップ
最新の日記
ユーザー登録
ヘルプ
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個与えられます.
各円錐は, 円錐の高さと, 円錐の半径が与えられる.
以下の例は, 帽子が作れない例と作れる例です.
このとき, 最大でいくつの帽子を作ることができるでしょう.
解法
各円錐をグラフのノードとみなします.
上側の円錐のノードと, 下側の円錐のノードとで, 帽子にできるペアをエッジでつなぎます.
あとは, このグラフについて, 二部グラフの最大マッチング問題を解けばいいです.
グラフはこんな感じになりますね↓
Med
開けずに帰りました
My Comment
反省点
英語読むの遅いです.
アジア地区もあるので, 英語の勉強しましょう.
よかった点
貪欲をやらずに, 確実性のある二部マッチングで解いていたのはよかったでしょう.
でも, 貪欲解法思い付けた方がいいですね.
コメントを書く
ちょっとしたコメント
トラックバック - http://topcoder.g.hatena.ne.jp/Respect2D/20120709
リンク元
110
http://topcoder.g.hatena.ne.jp/
95
http://t.co/wzWKhBdv
4
http://topcoder.g.hatena.ne.jp/kagamiz/
3
http://favstar.fm/users/iwiwi/discovered
3
http://longurl.org
3
http://ja.favstar.fm/users/Respect2D
2
http://hootsuite.com/dashboard
2
http://topcoder.g.hatena.ne.jp/diarylist
2
http://www.google.co.jp/imgres?um=1&hl=ja&sa=N&rlz=1C1LENN_enJP441JP441&biw=747&bih=704&tbm=isch&tbnid=1NOIGFdfMCo6vM:&imgrefurl=http://topcoder.g.hatena.ne.jp/Respect2D/20120709&imgurl=http://cdn-ak.f.st-hatena.com/images/fotolife/R/Respect2D/20120710/20120710002406.png&w=800&h=596&ei=bb5FUPLDDM-VmQXG5YGIDw&zoom=1&iact=hc&vpx=446&vpy=49&dur=4122&hovh=194&hovw=260&tx=164&ty=142&sig=110924746547802967822&page=1&tbnh=160&tbnw=215&start=0&ndsp=9&ved=1t:429,r:2,s:0,i:77
1
http://twipple.jp/
<前の日
|
次の日>