Hatena::Grouptopcoder

hotpepsiの練習帳

2013-06-03

SRM 580

01:37

Div1 Easy (250) EelAndRabbit

問題

  • 地点Xにうさぎがいる
  • N匹のうなぎがいる
  • それぞれの長さはLで、時間Tに地点Xに頭が到達する
  • うさぎは、2回までうなぎをつかみどりできる
  • うなぎを取れる最大数を求める

方針

  • うなぎの頭としっぽの座標の合計2N個の座標で全探索
  • ある座標のときに捕獲できるうなぎをbitでリストXに保持しておく
  • リストXの任意の2つの組み合わせのbitの論理和で、ビットが立っている最大数が答え
  • 提出
  • Passed System Test
  • (終了後)
  • 単純にforループでまわすだけでよかった
  • かつ、頭だけ調べればよい
  • というのは、同時に捕獲できる場合、その範囲内には必ずどれかの頭がかかっているから
  • https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_580/EelAndRabbit.cpp

結果

o-- 171.88pt 483rd/796 rating 1266 -> 1300

うなぎの問題が通ると嬉しい!

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20130603