TCO Marathon Match Round2反省記

去年に引き続き、今年もround2で敗退しそうだ。

わざわざブログに書くほどの工夫をしたわけではないが、一応やったことを書いておく。

1. 3点をランダムに選ぶ。

2. 3点の外接円をつくり、その周上にある点を選ぶ。

3. 2.で選んだ点に対して正多角形ができるかDPで探索する。

4. 凸性の検査と、重心からの距離判定を行う。

1. - 4.までをループでまわす。最初は、10角形以下は捨てるようにする。その後、この閾値を、9,8,7,..,3と下げて行く。

ちょっと工夫した点としては、

・すでにfixした点をactive集合から外して、探索から除外されるようにする。

・n角形の閾値の他に、距離閾値を設け、3点間の距離が近いものから優先探索するようにする。

・外積を利用して凸性の判定を実施することで、線形オーダーで判定する。（Testerは、O(n^2)だった。）

ぐらい。

まー、こんなもん。

上位陣は、多角形の探索を、2点と辺の数を固定して行っていた模様。確かにその方法だと、自分のやり方より明らかに速い。（自分の処理の2.3.でやりたいことが、2.だけの計算時間でできる。しかも3.は一番オーバーヘッドが大きい処理だった。。）

アイディア負け感が強いが、それ以前にに大きなミスをしていることに、コンテスト終了後に気付いた。

今回のコンテストは、相対評価のスコア。自分は、絶対ポイントの総合点が最大になるようにパラメータを設定していた。

で、こんな現象が起こってしまったと考えている。（表の数値は実際の点数と全く関係ありません。）

	case1	case2	case3	case4	case5
competitor average	100	1000	20000	300	3000
my score	80	990	22000	210	3300

これだと、total scoreではいいチューニングかもしれないが、全体としては負けてる感が。。

そもそもsmallとlargeケースで、チューニング分けろ！

てかその前に、各ケースごとに自分が作ったプログラムを評価しとけよ！

と、かなりダメダメな感じでした。

コンテスト終了後、chokudaiさんが、「上位陣と自分の各テストケースにおける優位性をしらべるために何回もsubmitしていた。」と発言しているのを見て、自分の調査の甘さにしょぼぼーーんってなりました。。

しかし、今回のmarathon matchでは、得るものが多かったのも事実です。

• オーバーヘッドの見極め方
• 最適化の仕方
• gettimeofdayの落とし穴

など今までになかった知識、方針などが身に付きました。

特に、gettimeofdayは、過去のmarathon matchでもサーバー遅いなと思いながら戦っていただけに、解決出来てかなりすっきりしました。gettimeofdayを呼ぶ回数を少なくする方法で解決したのですが、他にもいい方法があるみたいなので、それについては、いつか改めてブログに書きます。

(追記)

結果でた。まさに予想通りの現象が起きていた。平均点数が高い問題に対しては、自分の解法はかなり高い点数を取れていた。しかし、それ以外の過半数の問題に対しては平均以下のようだった。。

次回から、問題・スコアリングの特性に適したパラメータチューニングを心がけよう。