hotpepsiの練習帳

SRM 508 Div2

01:58

Easy (250) CandyShop

問題

• キャンディー屋の候補が座標で与えられる
• 可能性のある座標の数を求める

方針

• 本番: 配列で持つ(範囲が間違っていて失敗)
• 解きなおし: 1番目の座標(x0,y0)の範囲内に対して、全(xn,yn)が条件を満たすかどうかを調べる

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_508/CandyShop.cpp

反省点

• きちんと最大範囲を確認すること

Medium (500) DivideAndShift

問題

• N個の駒と、M番目が与えられる
• 素数による除算か、左右いずれかのシフト(ローテート)が可能
• M番目の駒をいちばん左端に移動するための最小コストを求める

方針

• 除算して位置が大きくなることはないので、シフトは最後にやればよい。
• 本番: 素因数分解して総当り(間に合わずに失敗)
• 解きなおし: 2からNまでの全ての除算可能な数で割ってみて、それらの最小コスト(素因数の数+シフトの数)を求める

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_508/DivideAndShift.cpp

Hard (1000) YetAnotherORProblem2

問題

• R以下のN個の数値において、和と論理和が等しい組み合わせの数を求める。

方針

• 途方に暮れる
• 写経!
• j以下について、bitの部分集合のうちR以下のものを加算、というループでいける
• 和はRを超えるケースがあることに留意する
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_508/YetAnotherORProblem2.cpp

感想など

x-- 142.02 1028 -> 955

• Mediumむずい。
• 素数テーブルが手元になかったので、エラトステネスのふるいと、試行除算で実装して速度を比較したりしてみた。エラトステネスのふるいが想像したよりも速かった。
• MediumではM番目が与えられるが、mod演算するため、0-based indexにしておく。
• 右シフトでのコストは、最も右のN-1にあるときに1なので、indexをmとすると、(N-1 - m)+1つまりN-mになる。
• 素数表は1000000まで作っておく必要あり。System Testには最大の素数(999983)が入っている。