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