Hatena::Grouptopcoder

hotpepsiの練習帳

2011-06-12

SRM 508 Div2

01:58

Easy (250) CandyShop

問題

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

方針

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

実装

反省点

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

Medium (500) DivideAndShift

問題

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

方針

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

実装

Hard (1000) YetAnotherORProblem2

問題

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

方針

感想など

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)が入っている。
トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20110612