hotpepsiの練習帳

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

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