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を呼ぶ回数を少なくする方法で解決したのですが、他にもいい方法があるみたいなので、それについては、いつか改めてブログに書きます。

(追記)

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

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

TopCoder Marathon Match Local Tester

Marathon Matchのローカルテスターを作った。

TopCoderのサーバーでテストすることは出来るのだが、

• 2時間に1回しかサーバーでテストできない。（Example testの場合は、15分に1回）
• queueに人が溜まっていると待たないといけない
• 採点されるテストケースは、Full Submit Testのテストケースより多い

の理由からローカルで自動テストスクリプトを作って走らせる人が多いようだ。

昨年のTCOで作ったはずだが、どこかに行ってしまったので今日作った。今度はどこかに行ってしまわないようにブログにあげておく。

テストを走らせる処理は、windowsのバッチスクリプト

テスト結果のパースはperlで書きました。

ローカルマシンよりTopcoderサーバーの方が断然早いのでTime Limitについては何らかの補正が必要か？？

@ECHO OFF

echo System Test Starts..

:: set variables
SET MAX_SEED=100
SET SEED=0
SET OUTPUT=%1.txt

:: solve problems
:LOOP
echo Solving #%SEED% ....
IF %SEED%==0 echo SEED = %SEED% > %OUTPUT%
IF NOT %SEED%==0 echo SEED = %SEED% >> %OUTPUT%

java -jar hogehogeVis.jar -exec "hogehoge.exe" -seed %SEED% -novis >> %OUTPUT%

SET /A SEED=%SEED%+1
IF %SEED%==%MAX_SEED% GOTO LOOPEND
GOTO LOOP

:LOOPEND
echo System Test Ends!
echo -----------------------
echo [Overall Result]
perl parse.pl %1

open(INPUT, "<" . $ARGV[0] . ".txt");

@list = <INPUT>;

$pointSum = 0;
$timeOver = 0;

foreach $line( @list ) {
    if ($line =~ /(^Time)/) {
        $line =~ /([0-9\.]+)/;
        $time = $1;
        if ($time > 10) {
            $timeOver++ ;
        }
    }
    elsif ($line =~ /^Score/) {
        $line =~ /([0-9\.]+)/;
        $point = $1;
       
        $pointSum += $point
    }
}

print "Point: " . $pointSum . "\n";
print "Time Over: " . $timeOver . "\n";

MAX_SEEDは、TopCoder上のFull Submissionでは100、System Testでは1000くらいだと思う。