Hatena::Grouptopcoder

hasiの日記

2010-05-09

Marathon Match 59 - BookSelection

06:04

今更だけど。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14227&pm=10885

本棚に本を詰め込む。本にはそれぞれ価値があって、価値の合計が得点になる。本と本棚には幅と高さがあって、リンク先の図のように詰め込まないといけない。制限時間2秒。なんか短い。

手法

DPとか貪欲とか使って適当に詰めた。

DP

ナップサック問題のDP。一段に入れられる最適解を計算。

貪欲法

整数計画なのを線形計画にすると貪欲法で最適な値が得られるはず。たぶんDP<=貪欲法になるのでこれで枝刈りできる。

手順

大雑把に。

  1. 価値の合計/(段の高さ+10)が最大になるような段の高さを求めて本を詰める
  2. 本が入らなくなるまで1.を繰り返す
  3. 1.と2.で求めた段の高さを元に、高さの小さい段から本を詰め直す
  4. 適当にそれぞれの段の高さを決めて、高さの小さい段から本を詰めて、結果が良くなったら更新
  5. TLEしない程度に4.を繰り返す

結果

53位。Rating: 1763 → 1769

2010-04-16

Marathon Match 58 - IsolatedPrimes

17:09

遅くなったけど、最終結果も出たので書いてみた。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14226&pm=10844

x,a,bが与えられたとき、p-a以上p+b以下の素数の数がx個以下となるような素数pを見つけろ、pは小さければ小さいほど高得点、という問題。ただしxは1以上500以下、a,bは4x以上25x以下。

手法

素数を小さいほうから列挙して、条件満たした素数を見つけたらそれを返す。それだけ。

エラトステネスの篩

言わずと知れたなんとやら。

区間篩

たぶん区間篩。自力で考えたけど、車輪の再発明だった。

埋め込み

P[] = {2,3,5,7,11,…}として、x=X, a+b+1 <= P[i+X+2] - P[i] - 1ならば(P[i], P[i+X+2])に解がある可能性がある。逆に、a+b+1 > P[i+X+2] - P[i] - 1ならば、P[i+1]~P[i+X]でX個、という解にはならない、ということがわかる。

これを元に、xとa+bが与えられたときp-aはこれより小さくならない、ということがわかるので、手元で計算して区間篩の開始位置として埋め込む。

x = Xのとき、a+b <= C[0]ならば9から開始、a+b <= C[1]ならば299209から開始、…といった具合。

その他

もっといろいろ書こうと思ってたけど面倒くさくなった。

ここをもっと詳しく説明しろ、というのがあったら気軽にコメントしてください。

結果

18位。Rating: 1624 → 1763

TopCoder部に入部した

17:07

d:id:staebchenです。サブアカウントを作りました。

http://twitter.com/hasi_tに合わせてhasi_tに。TopCoderではhasiです。

よろしくお願いします。