Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-10-02Marathon Match 65

Marathon Match 65

| Marathon Match 65 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - Marathon Match 65 - hama_DU@TopCoderへの道

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14355&pm=11122


問題の概要

tomerun氏が参加記録を書いておられるのでそちらをご覧ください。

http://topcoder.g.hatena.ne.jp/tomerun/20100929


とりあえず

オーダーの数(orderCnt)は実際に使うべきブロックの数よりも多いので、以下のようにしきい値(threshold)を概算。

int take_order = (width * height - bad) / K;
double threshold = (1 - ((double)take_order / orderCnt)) * 100;

badははじめから使えないブロックの数。

それぞれのオーダーで、これより少ないincomeだった場合は採用せず。

もし採用する場合は、左上から順に探していって、埋められるところを見つけ次第そこに埋めた。


これで出したのがトップスコアの75%。


時間をめいっぱい使う。

init(初期設定)時に、ある程度ブロック配置の計画を立てるべきではと思った。

ブロックを左上から使うことを前提にして、使うブロックの順番を配列にし、シミュレーションを行った。

配列シャッフルしながら15秒ほど探索を行い、空きのマス数が最も少ないブロックの埋め方を採用。


オーダー時に、thresholdを満たすブロックで、

上記探索結果に使われているブロックが出現した場合は、そこに使う。

ブロックが探索に使われてなかった場合は、少々もったいないが無視した。


オーダーごとにthresholdを再計算し、

もともとのthresholdを5下回ったら、左上から順番に探すモードへ移行させた。


これで80%まで行けた。


効率よくブロックを埋めるには。

左上から埋める場所を順番に探すときに、K未満の空きスペースができてしまう場合は、

その場所は採用しないように改造した。

だが、時間的に間に合わないケースもあったため、合計時間が19sを超えた場合は、

空きスペースを考慮しないモードへ移行させた。


これで85%

その他にやったこと。

ブロックごとに重みが設定してあるため、はじめ、オーダーの10%はweight観測に使い、

ブロックごとにthresholdを計算しようと思ったが思ったよりも点数は伸びなかった。


後はthrehsoldの調整を行ったり何なり。


ソース

githubに揚げました

http://github.com/hamadu/topcoder/blob/master/mm/mm65/CuttingFigures.java

2010-05-10Marathon Match 58/59

Marathon Match 59

| Marathon Match 59 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - Marathon Match 59 - hama_DU@TopCoderへの道

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

指定された大きさの本棚に、本をなるだけ効率良く詰める問題。

本ごとに大きさと点数が決まっているため、

なるだけ効率のよい本(小さくて点数の高い本)を

ふんだんに使うことがポイントとなる。


とりあえず

点数の高い順に本棚に詰めていくプログラムを書いてみた。

提出。35.2万点。


高さ的に残念なことになっている本同士を入れ替える

異なる棚にあって、本同士を入れ替えても幅をオーバーせず、

棚の高さを節約できる場合は入れ替え、高さを稼ぎ、

余った本を使って残りを埋めるプログラムを書いた。

提出。36.8万点。


点数の高さよりも、効率のよい本を使ったほうがいいかな?

本を点数効率(=本の点数÷本の面積)の高い順に入れ替えて、

上記と同じ手法を試してみた。するとローカルテストで40万点代突破!

きたこれ。

この後、ある棚の本に対して、複数の本で入れ替えたほうが点数がいいなら

それらで置き換えたり、点数効率の上位のみしか使わないようにしてみたり、

その他パラメータをいじくるも、あまり点数は伸びず。

提出したものは40.3万点を獲得。


本を高さでグループ分けしてみる

高さが76~80の本、81~85の本、86~90の本・・・という風に

本をある一定の範囲の高さでグループ分けして、

同じグループの本を隣通しで使ったら効率がいいのではないかと考えた。

どういう順番でグループを本棚に入れるかを深さ優先探索し、

残り時間が0.15を切ったら、パターンのうち最高得点を出した組み合わせを暫定解とし、

後は本を入れ替えたり高さを稼いだりごにょごにょする・・・

というプログラムを書いた。

これならば、高さがあまり無駄になることがないのではないか、と。

範囲を15に設定して提出。42.9万。きました!


暫定解を求めるときに

最高得点の更新の様子をローカルテストで確認したところ、

ある程度点数が更新されると、時間切れ(1.85s)まで更新されないことに気づいた。

そこで、一定時間最高得点の更新がない場合は、

暫定解の探索を打ち切るようにしてみた。

ローカルで試してみると、あまり点数は落ちなかった。

そこで、グループ分けのパターンを変えたものを3通り用意し、

それらについて暫定解の探索を行うようにしてみた。

  • 高さが76~80の本、81~85の本、86~90の本
  • 高さが77~81の本、82~86の本、87~91の本
  • 高さが78~82の本、83~87の本、88~92の本

のようにグループとする高さを少しずつずらしたものに対して

探索を行い、最もよい暫定解を元に

本を入れ替えたり高さを稼いだりごにょごにょする・・・

というプログラムを書いた。

現状このアイデアでは、グループ化範囲を5に設定したものが

最も高得点がとれたので、提出。45.5万。

暫定解探索時の枝狩り

暫定解を探すとき、棚の途中でグループの本を使いきってしまった場合は、

仕方なく他のグループの本を使うことになるのですが、

この使うグループの高さが余りにもかけ離れている場合は、

「どーせ大した点数こないだろ」ということで探索を打ち切るようにしてみた。

これでパラメータを調整しつつ提出。45.9万。頑張った俺。


結果

94位/312人。しょっぱいなぁ。

rating微減するも何とか黄色キープ。(1578→1559)



Marathon Match 58

| Marathon Match 58 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - Marathon Match 58 - hama_DU@TopCoderへの道

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

連続した自然数の中で、素数の出現率が薄いところを見つける問題。


とりあえず

ある素数が x-isolated であるか判定するプログラムを書き、

それを2から順番に回してみる。

しかしこれだと xが小さい場合や、 a + b が大きくなる場合に

答えが出せなくなってしまう。そこで、求める素数の出現率( x / (a + b) )が

ある一定値以上である場合は先頭から順に探索。

そうでなければ探索開始位置を倍々に増やしながら

10万ずつほど探索するようにしてみた。

これで出したのが22点ちょい/100。


x-isolated判定高速化

ある範囲(p - a <= n <= p + b)の素数の有無を判定したら、

nを1増やす際の素数の数はp + b + 1 が

素数であるかどうかだけわかればよい。

これでだいぶ速くなった。

2から順に探索する場合の範囲を緩めて提出。50点ぐらい/100。


埋め込みを使う

xに対して、a、bを最大にとった場合の答えを埋め込むことにした。

これにより、a、bにどんな値が来ても、答えは必ずその数以下となるし、

なにより答えが出せずに0点ということがなくなる。

以降はアルゴリズムの改良と同時に、

なるだけ小さい値の埋め込みデータの探索にいそしんだ。

結果は51点ぐらい/100だった。


エラトステネスの篩で素数テーブル生成

をすることにした。

範囲を限定して数が素数であるかどうかを

あらかじめ求めておくというアイデア。

しかしメモリの使用制限があるため、

生成できるテーブルの大きさは512M。

探索範囲を倍々に増やす場合は、

まず512Mの素数判定テーブル生成

→その範囲で順繰り探索

→次のテーブル生成...

という処理を繰り返すようにしてみた。

テーブル生成に2sほど時間がかかるのがネックだが、

あてずっぽうにやるよりかはいいはずだ。

これで提出!52点!ヽ(・ω・)/ ズコー


そして

ひたすら埋め込みデータを作成。

がんばったけど点数は一向に上がらなかった。


結果

480点!48位/375。まぁそこそこか。

これで初回ということもありratingが黄色になりました。(1200→1578)わーい