Hatena::Grouptopcoder

chokudaiの日記

 | 

2011-06-01

TopCoder Open 2011 Marathon Round 2

00:42 | TopCoder Open 2011 Marathon Round 2 - chokudaiの日記 を含むブックマーク はてなブックマーク - TopCoder Open 2011 Marathon Round 2 - chokudaiの日記 TopCoder Open 2011 Marathon Round 2 - chokudaiの日記 のブックマークコメント

06/02

注意

06:51くらいまで、問題誤読が発生しています。

02:00

問題確認

  • 点が大量に与えられる
  • 多角形を大量に作りたい この面積を最大化
  • 正多角形に近くないとだめ その基準がsidesDiffとradiiDiffで、許容される相対誤差みたいなのが与えられる

問題自体の把握は結構容易に行けた。直感は焼きなまし

点を使いすぎると勿体ないから、基本は正三角形の量産を目標に

02:20

適当な1点を選んだ時に、「この範囲に点があれば確実に作れるよ!」みたいなのがありそう

外側から順番にこれを詰めていく、みたいなのは無理かなぁ

とりあえず、外の方にある奴を優先して詰めていきたい これは確定

殆ど貪欲でも良いくらい?

02:24

まてまてまて、入力サイズを確認せずに思考してる

  • 点の数 50~499が50% 500~5000が50%
  • sidesDiff, radiiDiffはともに1~20% 1て相当厳しいなぁ

なんかx,yの選ばれ方が不自然っぽい?英語が読めないからここはソースコードを確認

中心決めてr+dD*正規分布で飛ばすらしい rが30-270 dDが10-100っぽい はみ出る・重なるでやり直し

02:37

一応点はドーナツ状に配置されるようにはなってるのね

いやしかし中心点は5~20個ランダムで作られるらしいし、乱数もでかくないかこれ?

あてにしないほうがよさそう

02:47

700*700で整数しかないなら、10*10くらいのブロック作るのが妥当だろうなぁ ブロック数が70*70の4900個 点の数は最大5000個 ちょっと多いかなぁ、と思えるラインだけど ここのサイズは可変かな

ランダムに残ってる2辺選んでごりごり探索、とかでもまぁそこそこの点数にはなりそう

02:50

3角形が量産できるならそれに越したことはないんだけど、sidesDiffが大きめ、radiiDiffが小さめな時に、3角形は作れるけど6角形が作れない、ってあり得るのかなぁ

基本有り得ないと思ってるけどあんまり自信がない

多分最初は3角形オンリーで十分戦えるんだけど、ある程度レベルが上がってくると、四角形入れないと話にならないんだろうなぁ 多分問題サイズとか制約によるよね

02:56

radiiDiffって角度っぽいのだとばっかり思ってたら、これ中心からの距離なのか 中心とか言う概念出されるとちょっと辛いなぁ どう弾けばいいんだろ 幾何力弱い

  • 必要調査

radiiDiffとsidesDiffに対して、正多角形(主に三角形と四角形)がどの程度作り辛くなるかの調査

ランダムの生成方法に、三角形の作り辛さがどの程度影響するかの調査

03:08

計算で出せるかなぁ、と思ったけどちょっと辛そう

多分調査範囲はsidesDiffとradiiDiffの調査結果を適当に利用するから、後ででも十分

現時点まとめ

・外側の点から貪欲に三角形を生成 作れなくなったら四角形を生成

・適当に消す→増やすの繰り返しで焼きなまし

まぁここら辺が妥当な解決方法なんじゃないかと

調査前に結論を出すのは早計だけど、実際にこれをやるなら、提出ソース組んじゃってどの程度のパフォーマンスが出るか調べた方が早い

評価方法が勝ち負けでの相対評価なのがちょっと嫌だけど 得意ケース押し付けゲーでなく、苦手ケースしらみつぶしゲーになるのは基本的にクソゲー 最近多いよね

03:13

いやいやいやちょっとまて、外側の点から選べば距離が遠くなる、は安易な考えだ

自分が欲しいのはあくまでも「長い辺」であって、これが達成できるやり方にしないといけない

・・・ってことは、必要なのは、辺の長さに対してソートして、その長い順に処理、だよね 多分

辺の本数はN(N-1)/2で、50の時1225本 5000の時12497500本 うん、ぎりぎりソート可能かな

5000の時は色々と危なっかしいけど・・・NP=5000 bothDiff=20で死にそう 大丈夫かなぁ

20って8割許容だから、相当広い範囲から取れるしなぁ

まぁ30秒TLEだから、1回は取れるはず 1回で十分かって言われると色々あれだけど

03:18

探索の打ち切り方は、見つけた瞬間打ち切りで十分の予定

基本的に、その辺より長い辺で打ち切れることは有り得ないはずだから、妥当な点から広がる方向に縮めて行けばOK

うーん、今の実装だと貪欲1回で終わりそう ここからどうやって発展させていくか

偏り持たせた乱数列生成すれば何とかなるかなぁ

03:27

とりあえず上記実装で組んでみよう

初日スコアとしてはそこそこ良いのは出るはず?

03:28

すでに4人が提出している

それぞれ点数が、78.17 72.17 34.33 11.00

はて、4人の時点でどうして点数が.17とか出てるんだろうか

3人が有効な点数で、ドローの点数があると0.17点 これが出てる? ・・・と思ったけど勘違い。0.5+0.67で1.17 普通に出るや

04:05

とりあえずPとEのクラスを作ってEをソート TLE あちゃーw

一定以上長い辺のみを使ってソートとかかなぁ

とりあえず、最大辺長は700*√2=1000くらいで、三角形を作るのに有効な辺は、えっと、正方形に収まる最大の正三角形ってサイズどれくらいだろ?

700*(√6-√2)で710くらいっぽい これは驚き 誤差考えて710*(1/(1-sidesDiff))あたりが上限かなぁ 最大長は逃したくないし

で、下限だけど、辺が100000個以下くらいになることを目指そう 適切な基準点見えないけど どうすりゃいいんだろ

10000個くらい乱択して、その中の何割ーって適当に選べば良いか 何度もやる処理じゃないし

その辺で出来る正三角形が枠外に出過ぎ、みたいなのも判定そんなむずくないし行けるかな

04:49

枠外に出てる判定がそんなに重くないので、長さ判定が要らない気さえしてくる いや微妙?

基本的に、長い辺の方がOKな点の範囲が広いわけだから、作りやすいはずだし、今の長い辺から潰していく方針は適切なはず

とりあえず初日から睡眠削りすぎるのもよくないかな?とりあえず今日は寝て夢の中で考えよう おやすみなさーい!

05:14

起床 続き書くよー!

radiiDiffが使いにくい!どうしようかなぁ・・・統一したい

06:51

なんかやたら点数が伸びないと思ったら、サイズを面積と読み間違えてるやん!

サイズは、頂点数の二乗らしい となると多角形見つけないと全然だめやん みょーん

07:27

問題読み間違いがあって酷い事になってるけど、"面積最大化"のコードを送信

大した順位にならないことが自明だから気楽

Submit 1: Overall score: 45.22 (6/10)

16:28

ようやくマラソンに復帰

n角形の作り方を考えないと話にならないなぁ

とりあえず三角形とn角形の違いを纏める

  • 辺の長さが短くなるため、sdの影響が大きくなる
  • 逆に、rdの影響は小さくなる

さて、これを踏まえて、最大何角形くらい作れるもんかなぁ

一辺決めて、中心点を定義して探索、いや探索だと無駄に時間かかりそうだから、発見次第打ち切り?

rd,sdの現時点に対して現時点で何%影響しちゃってるか、とかの最小の奴を選択、でよさげかな

DPも可能?sd=20とかの時に探索空間爆発してどーんってならない? 凄くなりそう

16:36

とりあえずその前に、さっき考えた最大何角形くらいまで作れるかをきちんと詰めるべき

n角形でnが大きい時、気にするべきはsd

整数の点にしかないわけで、要求が0.5,0.5みたいになった時に、ズレる長さはまぁ大体0.7くらい

これが20%の半分の10%になる辺の長さは7

700*700に辺の長さ7ですっぽり収まる辺の長さは・・・314角形くらいだなぁ

まぁ理想論にも程があるわけで 5000点均等分布の場合も考えてみようか

これだとさっきのを70*70に縮小してあげれば良いわけで、31角形くらい これくらいは実現可能そう

普通に3角形をたくさん作ると15000点のところを、1個31角形作るだけで961点くらい来るからだいぶ違いそう

実際は環状に配置されるような偏り作ってるっぽいし、100まで・・・は微妙?でもそれくらいまであり得る感じ

16:38

しまった、凸でなければならない、って条件を忘れていた

これが入ると一気にnが大きいn角形は作り辛くなりそう

あと、1つに絞るとnが大きいの死ぬの確定っぽい うーん DPぽいことしないと行けなさそう

17:00

というかむしろ、10角形くらいは点が多いならぽんぽん作れるんじゃないか、ってことに注意するべきなような気も

必死に30角形1個作っても、その間に10角形100個作られたら勝てないよね、的な まぁ最終的には両方作らないと勝てない気もする

17:12

んー、多角形の途中のm点(m≧3)のみの情報で、暫定的な中心が作れれば楽

隣り合った3点から作られる円の中心を集めてその重心とか?

とりあえず、三角形を作るくらいは後でいくらでも出来るから、おっきいのを如何に高速にたくさん作るかが大切

まぁ余る点が出来ちゃう可能性はあるから、三角形作ったのは消して作り直して、の焼きなましっぽいことはやってあげても良いかもね

17:43

以下sidesDiffをsd,radiiDiffをrdと記述

長い辺の方が当然自由度は高くって作りやすい

短い辺の方が自由度が落ちるけど、n角形が作りやすい

1つの辺の長さをLとして、これでN角形が作れる確率は、とりあえずrdを無視して、大体有効範囲が(L*sd)^2としちゃうと、NPの格子点あたりの存在確率がNP/49000とかでこれをnpとして

(1-(1-np)^( (L*sd)^2) )^(N-2)とかになるはずなんだけどなんだこれ 概算のつもりがやたらめんどい

とりあえずNP=0.01として、辺の長さ50で30角形くらい作ろうとすると、0.9994286477930963362428

あれ、大体作れると主張された うっそだー

sdを半分にしてあげると0.15 それにしても作れすぎ? 実際は多分半分くらいになるはず

まぁ現実的に許される誤差はsd/2だろうし、30角形はだいぶ無茶、みたいな計算で良いのかな?

(無視というか、その長さの比は、cos(2π/n):cos((2π-2π/n)/2)とかそんな感じだろうから、大体rd/cos(2π/n)*cos((2π-2π/n)/2)してあげればsdに変換できる もちろんこれは嘘っぽい部分もあるけど)

もちろん長さ10だと4.83245126587538116812E-13 1辺の長さの重要性がよくわかる感じ

17:59

sd=0.05で計算すると、10角形も危うい

これsdに応じて超別ゲーだなぁ・・・

20角形以上はさすがに考えなくてよさそう、って結論で、最大でも10角形くらいじゃないかな?みたいな感じ

いやまて、10角形ならLの長さあげられるのか えっと、200くらいまで?長さ100くらいあれば、挑戦していいn角形の上限が出せそう

これは、「枠に収まる範囲」と、「1%以上の確率で作れる範囲(これは多分要調整)」で、辺が長い場合、短い場合ともに抑えられる 上限高々15くらい、下限3(3も絶対無理、って出る場合もあるかも)

このそれぞれの最大値の大きいものを選んで探索していけば、そこそこ見つかる可能性は高め よし方針見えてきた!

18:05

現時点で憂慮すべき項目を列挙しよう 漏れがあっても後で書き足せば良いや

  • ある辺からn角形を探すことを前提としているが、それに対するクリティカルなアルゴリズムが現状思いついてない
    • これが現時点で最も致命的 逆に、これが思いつけば十分戦える
  • 分布の特性を考慮していない
    • x,yの最大値は取ってあげても良いんだけど、ドーナツ化みたいなことになると困るかな・・・
    • あとは4隅のどっかが抜けてるケースとか 作れる作れるって主張したいけど全然作れないパターン
18:06

中心の決め方をきちんとしてあげないと、ゴールに戻ってこれなくないか?

両端から詰めた方が良いのかなぁ うーん

20:27

なんか方針がここまでダメなのは初めて ちょっと慌ててる

とりあえず、中心からの距離のmaxをLmaxとして、中心(1-rd)*Lmaxの円と、L,maxの間に全ての円が収まることを前提とすると、仮中心を作って、その半径をLとして、(1+0.4*rd)Lと、(1-0.4*rd)Lの間に入ってる円の中にきちんと入っているかを確認してあげれば、とりあえずは何とかなりそう?

ある程度円の形を保たれてないとダメなのがrdの仕様だから円を最初っから決めてあげれば何とかなるっぽい

20:33

現時点まとめ

  • 作成評価関数を用いて、作成可能多角形の最大長推定を行う
    • 評価関数1:一様分布だと仮定した際の作成可能確率 (1-(1-np)^*1^(N-2)
    • 評価関数2:端点が内部に収まる最小サイズ これは作られる円がどの程度外に出るかで推測可能
      • 四角形以下は危険そうなので、 この場合は別関数で対処
  • 最大長が大きい辺ごとに、n角形の制作に挑戦する
    • 「1個前の頂点」「今の頂点」でDP 両方大した数にはならないだろう、という予測
      • 中央付近で探索して、10個見つけた時点で終わり、で100個までにしかならない
      • 保存するのは、sdが最小になっているもの 十分でないのは百も承知
  • 見つけたら即作成 貪欲に取り終わったらいくつか完成したものを取り除いて焼きなまし
    • 排除確率は、1/2^(N-2)とかで十分 6角形以上とかは大体そのままで良いだろうし
21:29

実装せずに色々確認中

正弦定理で大体円の半径は出せて、はじっこが決まってたら当然むっちゃ単調増加ではあるから、nで出来てn+1でない、ってのは確定

22:01

あんまりそのままでやると、3角形4角形に適用する時に微妙な気がする

・・・微妙になるやり方をしてるようじゃ勝てないのかなぁ

23:02

とりあえず組んでみて動かしてみれば良いかなぁ

多角形を拾う範囲の判定が今のところ相当怪しい感じ


06/03

04:03

なんか実行時間が間に合わないなぁ・・・

普通に初期設定部分で時間が全然足りない状態だから、ここどうにかしないと確実に死ぬ

04:15

とりあえずふつーに三角形のみで焼きなましてあげるのみのを送信

これで自分よりはっきりと上の人は、ちゃんと四角形以上使ってる人

Submit 1: Overall score: 72.92 (9/38)

予想外にみんなまだ適当だったみたい?四角形作るだけで1位行きそう

相対評価だからどんな感じだかいまいち判らない部分も多いけど

05:13

O(N^2)*おっきめの定数なinit部分をどうにかしないといけなそう

各辺全部を最初に走査するのは、N<1000くらいの時だけにしとくべきっぽい

それ以上の時は、前半部は適当にブロック分けしてそっちを代用とかかな?

大きい時はある程度正確だろうし、小さい時は距離依存の方が影響でかいしで、何とかなるんじゃね?

前半部は距離のみに依存だし、5以上だったら計算をちゃんとしてあげて、それ以下のは場合分けで何とかしてあげるとかで良いんだろう

30*30ごとくらいなら、まぁ妥当なあたりのが出るんじゃないかなぁ 30*30だと24^2ブロックくらいで、これの2乗ならそんな怖くない

12:57

ランキングを見るとltaravilseさんが1位 この人は自分の中で何となくヤムチャ的ポジションなので、誰もボーダーラインをまだ越えてないと判断

結構みんな苦戦してるのかな?だとしたら上のアイデア実装までで結構上位に行けるのかも

逆にこれを今日中に実装して1位になれないようだと自分が危うい 他の作業終わらせてとっととマラソンやろう

06/05

03:16

正直疲れ切ってるんだけど、ここで止まるわけにはいかないよね・・・

とりあえず方針は立ってるんだし、ただの実装くらいいくらでも出来るだろう・・・

それで上位がどの程度のスコアを出してるのかが判れば十分

三角形のみと、適当方針の点数比較もしたい

03:56

とりあえず25ずつ、28*28に分けて、点が1000以上の時はこの中心点からの比較でinit処理を行うことにした。

これがないと、各辺でのn角形制作可能予測がつかないから、これは必須

なんか、四角形以上のを実装する気がなかなか起こらない

今の方針に自信がないからか、それとも実装量で単純にやる気が落ちてるのか

04:08

2点から推測される円の中心点、っていうのは、どうとでも求まる・・・はずなんだけど、なんかそこでバグる こりゃ今日だめかも

もちろんこの中心点に自由度を持たせてあげることで探索範囲は広がるんだけど、それを自由に弄ると円の形を保つのが難しくなりそうだから、とりあえずは固定で

どこかしらの辺から中心固定すれば、ぴったり合うのがそのうち見つかるはず、くらいの甘めな予想

04:54

なんか気が変わった

調査が不十分なので、DPを取りやめて、近い点1個選んで突っ切る方針で

下手にDPやると計算量が怖い気がしたのと、そんなに効果が出ない予感がした あくまでも直感でしかないけど

06:40

実装おわり どうかな?

Overall score: 80.39 15/87

うん、これくらいなら良いんじゃないかな?

こんだけ適当な実装で、多分色々バグってる状態でこれなら十分過ぎる

1位が0.13、2位が0.21削れてるから、結構逆転ケース多いし、大差がついてるってわけでもなさそう

07:32

適当にやった感じ、

  • 生成可能多角形予測システムがまるで動いてない 多分バグってる
  • その影響か、無謀なのに挑戦して死んでるケースが多い
  • 単純に、頂点数の影響も大きいので、もうちょっとどう選んでいくかは考えるべき

というかそもそもちゃんと動いてるのか確認しないと話にならない

今後、多角形生成式がある程度進歩していったとしても、ここの計算式の精度で、今後の展開ががらっと変わる

07:46

円の大きさとかも焼きなましてあげた方が良いのかなぁ

ちょっと今だと作れる多角形の種類が多分実際より少ないので、そのあたりをどうにかしたい

07:57

やっぱり多角形生成確率判定式がバグってた 割る数とかが全然違う

治すと多少の効果がありそう? これだけ直して送信してみてもよさげ

08:21

や、治ってるかこれ?

なんか怪しげな挙動を繰り返してる 回転向きが逆の可能性もあるなぁ・・・

08:49

数値調整中

数値調整してると一緒に調査っぽいのが出来て、何が足りないのか見えてくることが多め

まだまだ組むことがたくさんある段階だし、ちょっと早いけど

09:00

使ったフラグを消し忘れてた アホかw

ってことは、rdをどれくらい狭めて扱うべきかの調整、やり直さないと駄目そう めもめも

0.5倍で狭めてやった方が効率良いよなぁ、とか思ってたんだけど、これもうちょっと広げてあげないと、うまく作れないのが出てきちゃう

まぁ完璧に、ってわけにはいかないだろうけど

06/06

色消えたからここから手抜で

f:id:chokudai:20110605194348p:image

こうして

f:id:chokudai:20110605194349p:image

こうして

f:id:chokudai:20110605194350p:image

こう!アルゴリズマーならこれでみんな判る!説明いらない!だいじょぶ!

06/07

13:08

四角形と五角形を小さいケースで全探索で探すようにして93点

double res2 = Math.Log(1e-11 * len * len, 1 - Math.Pow( (1 - np), (dist * (1 - sd)) * (dist * (1 - sd)))) + 3;

現状ここの調整に苦労してる 1e-9でも1e-13でも、ばらっばらのケースでベストが出たりする

分布の偏りの影響が大きいんだろうなぁ・・・

1e-13でベストが引けるケースは、推測よりも大きい多角形で作れちゃうケース(seed 23とか)

1e-9でベストが引けるケースは、推測したのが全然作れなくて時間が切れちゃうケース

この推測に無理があるとは思ってないんだけど、うーん うーんうーん

13:57

とりあえず、1e-13にして、明らかに弱い要素をリストアップ

seed 4 0.857175872倍

seed 12 0.87240647倍

seed 16 0.820985615倍

seed 22 0.877318651倍

seed 30 0.845179363倍

他の値は、0.94倍以上だったのでとりあえず保留

これについて、それぞれの情報を調べてみる 後時間2倍のスコアも併記する

seed 4  np 3646 nD 07 sd 14 rd 05 maxScore:25962 2xscore:27910

seed 12 np 3271 nD 10 sd 09 rd 05 maxScore:18363 2xscore:18853

seed 16 np 4454 nD 10 sd 17 rd 05 maxScore:33299 2xscore:38066

seed 22 np 4268 nD 11 sd 14 rd 06 maxScore:37414 2xscore:37333

seed 30 np 4098 nD 16 sd 20 rd 03 maxScore:23918 2xscore:31082

seed 30の例を見るに、rdが小さくsdが大きい時に、まるで対応出来てない模様?

これをどうにか出来れば相当スコアは上がりそう?

とりあえず、次の点の探索範囲に対してのrdの影響を強めておいた

動く範囲は、マンハッタン距離でdist*Math.Max(sd, rd/2); rdの影響はそこまで大きくないはずなんだけど・・・

ちなみに元は、Math.max(sd, rd(n-2)); nはn角形のn 根拠は、n角形の1辺は円周の1/nに近似できるから、

rd:sd = 1/2 : π/n = n : 2π よって、nが増えれば増えるほどsの影響力が小さくなるだろう、との予測から

sdに比べてrdは扱いにくいので、影響力を弱めて1:n-2くらいにした

14:34

が・・・だめ・・・!

ということでちょっと変えよう

妥当なのはMath.max(sd, rd*2pi/n);なんだけど、これで合う気があんまりしないんだよなぁ

これn<=6でsdよりrdのが強いのか それだと影響力強いのかな うーんうーん

15:13

結局だめ 納得いかないけど、期待値計算のところに、Math.Pow(10/rd,2)あたりでもかけておけばなんとかなるかなぁ

lenが小さくってrdが2やら3の時やらが怖いけど、こういう時に大きい数字は早々出ないと信じよう

21:23

調節するくらいならC++に移行して高速化を図った方が良い気もした

ということでとりあえず多角形生成関数の、最後の部分だけちょっと考えて配置するようにした ほんのちょっと

23:06

いやいやいや円書いてるんだったら円周上でDP一択じゃね!?

sdが20%も動くのに何で点の位置が固定であると勝手に予想してるの!? それはなくね!?

f:id:chokudai:20110607231628p:image

この黒みたいなのもふつーにあり得るのに、なんで即捨てしてるんだろう自分は!

んと、この場合、下の黒点が8/9π、赤点がπの位置だから、1/9πずれてるわけで、2/9πずつ進んでたら大体50%のズレ

sdの変化度が大きい程こういうことになりやすいわけで、今の定点固定はちょっと現実味がなさすぎる

うーん、どうしようか 6点以上で凄く弱いなこれ いや点の数が多いと5点もダメな仕様か

5点で最大でずらそうとしても、角度で近似して、100 100 100 80 80の92 92 92 92 92で24のズレだし、殆ど無視可能ではあるのかな・・・

6点だと100 100 100 80 80 80が90 90 90 90 90 90になって30のズレ

まぁ4(n-1)くらいズレると考えておこう 嘘っぽいけど

23:54

うーん、途中で目標点を適当に弄ってあげて、ゴールについちゃったらどんまい的なことをすれば何とかならないかなぁ

適当にやると、sdが20の時にぴったりsdに収まってる率が20とかだから、毎回目標距離を弄ってあげるくらいが良いのかも

06/08

02:00

一応中心点を弄ってあげたらそれなりの結果にはなった それなり

さすがに探索順序がぐっちゃぐちゃな気がしたので、探索順序をどうにかすることをちょっと考えてみようか検討中

要求される点からマンハッタン距離優先で探してるけど、rd考慮全くしてないに等しいし、探索順序もうちょい工夫したい

「ある点に行ってみて、ダメだったら1個戻る」とかも欲しいかなぁ それがあるだけで全然違うし

DPはやっぱりやり過ぎだと思う 確実に点は求まるけど、速度が話にならないくらい足りない印象

02:13

貪欲にとっていく際に、前のとの兼ね合いでダメだったケースだけリストに入れておいてあげれば、直前修正が可能っぽいなぁ

これをやってあげれば、

  • DPほど遅くない
  • 下らない選択ミスによる多角形生成ミスが大幅に減る

って感じで有効なんじゃないだろうか あんまり頂点数が多いとボトルネックになりそうでもあるけど、偏りがあるケースであれば、リストに溜まるのが0だから、貪欲と殆ど同じコストだし、惜しい時しか時間はかからないはず

探索順序はとりあえず後回し?良い方法が浮かばないや

現状5位 JacoCronjeさんのだけ、他の人の点数が上がっても殆ど点数が削れないのが恐ろしい 一人だけ方針違いに見えるし怖いなぁ DP的なのを想像してる

03:44

くめた!

Overall score: 94.63

良い感じだけどこれでも届かないと何していいかわかんないなぁ

多分C++に乗り換えると1位がだいぶ近づく感じ 速度がなー

06/09

22:42

何が悪いのか良く判らないので、とりあえず半提出 頂点数500↑の時だけの結果を得ようとして見た ちょっとせこいとは思うんだけどね・・・

現在の提出者は160人だから、100/160=0.625くらい ここから、半分に分けた勝率が計算可能。細かい計算は面倒になるからしないけど 大体90の人に対しては、元に入ってるのが0.56くらいで、0.31になれば良いんだから、0.25削れれば勝ち越してる感じ

後半は、0.56くらいに対して、0.43くらいになってれば良いんだから、0.13くらいで勝ち越してるはず

前半で勝ち越してるかどうかは、1番目と3番目で0.15の差があるか見れば良いのかな ほんとかな 多分ほんと

◎>○>△>▲>×

chokudai 91.72 --.-- 47.02

nhzp339 96.47 96.59 96.60 ▲×

RAVEman 93.61 93.81 93.67 ×△

JacoCronje 93.39 93.54 93.53 △×

doudouille 93.24 93.50 93.33 ▲○

rudradevbasak 92.85 93.08 93.01 △×

Psyho 91.73 92.02 91.75 ×◎

pieguy 90.57 90.81 90.69 ▲▲

EmK 89.51 89.74 89.63 ▲▲

murrayr 89.37 89.65 89.50 ▲△

O_O 88.54 88.89 88.69 △○

nika 86.26 86.60 86.39 ▲○

quimey 85.20 85.56 85.45 ◎▲

kphmd 85.01 85.46 85.28 ◎○

rahulgarg123 84.09 84.30 84.22 ▲▲

komiya 83.96 84.19 84.19 ◎×

redocpod 83.82 84.24 84.10 ◎○

ltaravilse 83.80 84.25 84.07 ◎◎

blackmath 83.01 83.37 83.24 ◎○

予想外に面白い結果

頂点数500↑で全敗に近いのが、nhzp339さん、JacoCronjeさん、komiyaさん

逆に、頂点数500↓で全敗に近いのが、Psyhoさん RAVEmanさんもかなり強そう

要するにどっちも伸びるのね・・・というより、どっちも中途半端なのね・・・w

とりあえず方針は色々あるっぽくって、多分前半Psyhoさん、後半nhzp339さんのプログラム、って感じでマージしてあげるだけで相当強そう

ってか▲▲多くね?直接対決負け過ぎじゃね?もうちょい順位低いべきなような気がw

23:12
  • 大きいケースで負けている場合

これは間違いなく、6角形以上の多角形を作るプロセスで負けてると思う

これで明確に負けてるのは今のところ3人で、ここをどうにかしないと勝てる気はあんまりしてない

頂点数決めずにDPとかしてるんだろうなぁ・・・

  • 小さいケースで負けている場合

これはいくつか考えてる

    • 5角形・6角形の生成速度の問題

現在5角形を確実に生成するプログラムを持ってるわけだけど、正直あんまり早くない

この全生成をもうちょっと早く出来れば活路は見えてくるんじゃないのかなぁ

    • やきなまし

ごめんなさい焼きなましといいつつ山登りしかしてないです><

ただ、正直自分は焼きなましをそこまで信用してなくって、試行回数50~200回くらいしか取れない状態で、単純な山登りでなく焼きなましを採用する、ってのはだいぶリスク高い気がしてあんまりやる気がしなかったり

6/10

1:33

焼きなましをやったらちょっとだけ伸びた

やっぱ大きいケース取れるようにしないとなぁ どう改善するか・・・

Psyhoさんから小さいケース全く取れないのは・・・どしよ?5角形6角形のを色々考えてるけど出来る気しないし!

というか取れてないってことは、今の5角形のに取りこぼしがある可能性が無茶苦茶高いよね

8:44

夢の中で浮かんだあるごりずむを片っ端から実装

  • 6角形以上はランダム要素を強く持たせているのだから、何週かさせる これは1周目の時間を用いて行う
  • 頂点500以下の場合、現在、目標点の中心から次の頂点を探索させているところを、順番をランダムに変更する。
  • rdの判定が甘いのに対して「隣り合う点同士の目標中心点との差」からごりごりする

全部だめ なんでじゃー! 最初の1個だけ一応若干のプラスかな・・・調整を全力でして、ようやく0.1点とかそれくらいだけど

16:11

ごりごり高速化してた けど凄く微妙な感じ みょーん

17:40

自分に必要なのは気分転換なのではないだろうか!

ということでちょっと構ってオーラをついったーで出してみたら、@meg05296たんが反応してくれたのでちょっと遊びに

ストレスのコントロールもマラソンでは大切だよ!

06/11

21:37

やっぱり今のプログラムは、rdに関する考察が甘すぎるんだろうなぁ・・・

ある時点で詰んでいたとしても、それを確認できるのが最終段階まで行かないと無理、っていうのはだいぶ良くない

これが改善出来れば良いんだけど、無理なもんかなぁ・・・うーん 仮中点からズレた時に色々アレなのはわかってるけど、うーん

22:46

途中結果を軽く可視化 やべぇ逆走してるΣ

なんか超鋭角みたいになって条件満たしてるよね!みたいな主張してるのがあった

GCJ終わったら、目標点と前の点との距離を比較して、前の点からの方が近い、とかだと絶望的なので、そこをカットしてみよう

06/12

10:28

逆走チェックとか色々実装してみたけどこれはだいぶ厳しそう うにょーん

ある時点での合計角度がこれくらいだとだめ、みたいなのはあると思うんだけど、ちょっと判らない みょーん

16:53

結局やってるのは細かい調整

1周目はrdのlimitを厳しめに見積もって、2周目から甘目に、みたいな対応をしてるけど、それで早くなるかというとそうでもなくって、最初に拾えない分逆に遅くなっちゃってたりして微妙な感じに うーん

ただの貪欲で1周終わっちゃうことが多いから、とりあえず1周を高速に 2周目からは慎重に みたいな感じ

21:00

C++に書き換え 遅い あれ・・・あれ・・・・あれーw

06/13

03:25

どうして1個前変更に拘っているのか!

最後のrdcheckで、まずそうなやつを適当に変えてあげればいいやん!

それまでアバウトでもどうにかなるやん!

ばーかばーか!よし明日組む!おやすみ!

05:55

組んだけど遅いし成果出ないやん!

なして!なしてなの!

多分同一辺から検証した際にアレなのが原因だけど!

ってことはあれか!ああすればいいのか!おお!全然メモになってねえ!w

07:55

とりあえず、細かい調整

実行時間が早く出来れば良いんだけど、出来る気がしない・・・うーん うにょーん

23:36

円ずらすとこがバグってた!これは小さいケースに大きな影響を与えてる可能性が

ということで修正中

06/14

01:05

んー、伸びない

前回までのは、垂直二等分線から外れるような形になっちゃってたんだけど、そっちのが良かったりするのかなぁ

横にズラすのはあんまりしたくないなぁ、と思ってはいるんだけど、うーん

01:24

調整で伸びないのであれば、目標とするべき点が間違っていたバグだけ取り除いてあげれば多少はよくなるかも?誤差範囲だろうけど

中心点の設定部分を直してあげて悪くなったら、それはもう今の円の生成方法を捨てるのが妥当 中心からランダムに適当に動かしちゃう

06:50

大差ない むぅ

よく考えると探索がかなり被ってる気がしたので、最初の1点より番号が低いやつは探索しないことにしてみた

この番号が常に同じ順序だと当然だめなので、これもシャッフルで

07:05

駄目、露骨に点数が下がる

3・4・5角形の判定のみであれば、確定で出せるからアリそう?

小さいケースのみはこれで高速化出来た

09:37

自分らしくなさすぎるプログラムだから組まないけど、中心と中心距離・辺長を決めてあげれば、フロー流して解けるよねこれ

1本引くだけならDPでも解けるよね それ貪欲に取ればまぁまず間違いないよね

んー、なんかそんな感じで解こうと思えば解けた気がする いや間に合わないかなぁ 間に合わないと信じたいけど

間に合わないと信じて使わなかったのが負けの原因になりそうな気が

10:22

計算が間に合わなさそうな時に、ぱぱっとカットするのを作成

これで多少はよくなる?たぶんだけどw→伸びた!

13:00

1周目の条件を色々厳しくして見た!伸びた!

15:00

探索範囲をちゃんと見直してみた!伸びた!

21:00

焼きなましの際に、なかったことにする多角形の基準を甘くして見た!伸びた!

21:17

・・・というか、あれ?ん?なんかむっちゃ伸びてね?

あれ?w

06/15

1:56

なんかふつーに伸びるね 20位→14位まで復帰 ほえー

あとは4専用と5専用を使い過ぎなのとかあるから、そこらをちょっと弄ってあげればそれだけで良くなりそうな感じ

2:28

焼きなましはするんだけど、作る多角形を5以下に絞った瞬間に(小さい多角形の焼きなましは高速に行えるので)、毎回焼きなまし中の状態を、最良の状態に移してあげるっ

これをすることで、とりあえずそこの前までの最良から小さいのを探せるから若干効率が良くなる

4:11

ローカルの結果とサーバー上の結果がだいぶ合わない んー?

08:51

今更sqrt外しの高速化

これ外す前から調節始めたのは失敗かもなぁ

思ったより伸びる、というか殆どの処理が長さ計ってるだけなんだから当たり前っちゃ当たり前

いやまぁこういう部分が適当でもある程度戦える、ゆるふわあるごりずむ的なのが自分の戦い方だから、こういうガチ高速化は凄く苦手なんだけど!

11:33

なんか、四角形とかほんとは作れるのに、作れないんじゃないかと勘違いしているケースが多い気がする うーん?

と思って修正したらスコアが全体的に馬鹿みたいに上昇した なんだこれ!

13:14

どうやら、「多角形のサイズ」と「1辺のサイズ」を誤認して、枠に収まる四角形のサイズを考えていた模様

受け入れる誤差を大きく増やしてあげたら、かなり大きくスコアが上昇した

3%くらい上がってるから、下手すると優勝争いに食い込めるラインじゃないか?

14:02

どうも、自分が正当だと思っている範囲より広い範囲で多角形が取れちゃうらしい

今の処理は、各辺の垂直二等分線から、多角形(実際は円に近似)の中心点をどこまで離しても、枠の中に納まっていられるか、みたいなのから、Atanで中心角を出して、中心位置を近似、ってやってるんだけど、この問題は当然誤差が出てくるから、そのあたりでもちょっと苦戦中

14:21

何倍かして対応してたけど、よく考えると、円で近似してるから、頂点数が少なくて、本当は飛ばせるところで引っかかってるだけなんじゃないだろうか、という結論になった

ということで、適当に+1してたところを+2に変えたら、ある程度正当な予測で正しい感じに わーい

余裕が出てきたら文章がまともになってきたw

14:44

と思ったら、案外うまくいってなかった

radiiDiffの方の誤差予想はかなり簡単ではあるんだけど、sidesDiffの方が難しい?

最左辺、右辺とかの速度はsidesDiffには影響されないはずなんだけど、それを入れてあげないとうまく調整されない うーん?

14:47

ちがうちがうちがう!中心点の予測には影響されないけど、中心点を予測して出来た最大の円に対して、作れるn角形のnが変わってくるんだ!

平均n角形が作れる四角形が出来たら、n/(1-sd)角形が出来る、って感じになるじゃないか ばーかばーか!w

さすがに影響がでかすぎるだろうから、/(0.5+0.5*(1-sd))程度だろうけど、このあたりは適当に実験して頑張る!

15:24

上位で相対評価である時は、「上位に勝つ」ことよりも、「下位に絶対に負けない」ことが大切

これがきっちり出来てないとまず上には行けないし、逆にこれが出来てれば、直接対決で負けていても十分勝てる

今回負けやすいと感じるのは、nが超多い時の速度勝負と、nが超少ない時の精度勝負の2つ。どっちも自信ないからせめてどっちかは伸ばしたいなぁ

18:30

とりあえず、現状の生成可能多角形予測システムとして、

辺が長い→少ない辺数ですぐ盤面いっぱいに

辺が短い→多角形がきちんと構成できる位置に頂点がある確率が減る

っていうのを利用した挟み撃ち的な戦術なんだけど、前者が間違っていたようなので、後者を再調整すれば伸びそう

ってことでやってみたら0.3点プラス wataたんが頭おかしい状態で届く気がしない

19:37

ソースコードを見直し中

なんか、探索をしていく際に、目標とする角度を、「残ってる角度(÷残りの頂点数-1)」で良いはずなのに、これに「最初目標としてた角度」を足して2で割ってる。

後半の、「最初目標としてた角度」のほうの正当性がない気がするので削除

こういう良く判らない思いつきで入れたのが後半まで残ってるのはどうなのかなぁ・・・

20:27

探索中に、予想した頂点位置とズレた分、中心位置を補正していく処理において、予想されていた頂点位置の算出が、すでに補正されている中心位置から行われている問題を修正

この2つの間を取るような探索なら確かに有用性はあるのかもしれない

23:00

そこら辺色々伸ばしたけど、なんか良く判らない点数変化をするから戻しておしまい!おつかれさまでした!


-->

*1:L*sd)^2

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/chokudai/20110601
 |