問題

www.topcoder.com

提出コード

https://gist.github.com/siman-man/2218aee9a4a99e3bc6c780dbb72066ba

方針

N と A の値からサンプリングの回数を決定
クエリーの投げる位置を焼きなましで調整
クエリーの結果からグリッドを生成している方程式のパラメータを焼きなましで求める

N と A の値からサンプリング回数を求める

サンプルの個数から大体これぐらいの mse スコアが出るよというのを事前に計算しておいて、ちょうどいい感じのサンプル個数を求める。 mse の推測値が悪かったのか N < 40 のケースだとうまくいかなかったので場合分け。もっと細かく調整できたと思うけど多分そんなスコア改善しないし面倒なのでやってない。（cover_rate は sample_count * 9 / (N * N) で計算してる)

      if (N < 40) {
        if (cur_cost > 4000 || cover_rate > 0.13) break;
      }
      if (N >= 40) {
        if (g_exp_mse[N - 20][sample_count] < g_exp_mse[N - 20][sample_count + 1] + sample_cost) break;
      }

mse の推測値

python の curve_fit を使って自分のソルバーがサンプルを取得した数に対してどれぐらいスコアが出るのかを予測する。スコアのグラフが指数関数に似てたのでそれで近似を行う。与えるデータは自分のローカルで何個か計算しておく。

# 指数関数を定義します
def exponential_function(x, a, b, c):
    return a * np.exp(-b * x) + c

def fit_exponential_function(x_data, y_data):
    # パラメータの初期値を提供します
    initial_guess = initial_guess_from_data(x_data, y_data)
    popt, _ = curve_fit(exponential_function, x_data, y_data, p0=initial_guess)
    return popt

def calculate_score(sample_count, a, b, c):
    return a * np.exp(-b * sample_count) + c

def initial_guess_from_data(x_data, y_data):
    # a, b, c の初期値を直接データから求める
    # a の初期値は y_data の最大値、b の初期値は 0.01 (小さな正の値)、c の初期値は y_data の最小値
    a = max(y_data)
    b = 0.01
    c = min(y_data)
    return a, b, c

こんな感じでデータを取って

sample_count,score
5,21483.71434
7,13698.45827
10,8337.7041
15,5314.86126
20,3673.76252
25,2867.07684
40,1446.79279
60,1007.06145
80,664.26452

こんな感じの結果が得られる

sample_count,predicted_score
1,43128
2,35842
3,29836
4,24884
5,20802
6,17437
7,14663
8,12375
9,10490
10,8936
11,7654
12,6598
13,5727
14,5009
15,4417
16,3929
17,3527
18,3195
19,2922
20,2697
.
.
.

この結果をコードに埋め込んで利用する。N ごとにデータを取ろうとしたけど途中で面倒になったので 5個飛ばしでデータを取った。（なので N = 59 の場合は N = 60 の結果を利用してたりする）

クエリーの投げる位置を焼きなましで調整

クエリーを投げる位置について焼きなましで調整した。

近傍は「ランダムにクエリの位置を変える」の 1つで、スコアは「各セルごとの一番近いクエリの箇所の距離の合計値」を計算してこれが最小になるようにした。

計算自体は BFS で行ってて最初の step は 8方向、あとは 4方向に移動

方程式のパラメータを焼きなましで求める

方程式の数は 50 で固定。遷移としては 3つ

ランダムに方程式を生成する（どの確率で生成するかはテスターの実装と一緒）
offx, offy を少し変更
rx, ry を少し変更

これらの変更のあとに得られたグリッドの値をクエリーによって得られた正しい値を比較してその差分が小さくなるように調整していく。50 で固定しているせいで、E が小さいケースにめちゃめちゃ弱いけど自分では E を推定することができなかったので仕方ない。

感想

推定系は毎回苦手。 rhoo さんの解法を見て「へぇ〜 UNet なるものがあるのか」と思った。大きな差で負けてるので何か見落としてるだろうなと思ってたけどそもそも自分の知識にないものだったので次頑張ろうという気持ちになった。あと、自分だけみたいだったけど artifacts がダウンロードできなくてサーバー側でどれぐらいの速度で動いているかが確認できなくて地味に不便だった。途中ジャッジサーバが止まってたけど停電で落ちてたっぽい。

seed 1 - 10 のスコア

Score = 23559.635786576706
Score = 1726.0470920138887
Score = 7705.3169154104025
Score = 7504.327035433278
Score = 8597.371075943804
Score = 2932.7803554454154
Score = 8497.537837936074
Score = 13487.69213050256
Score = 3508.515444010831
Score = 5008.201252074448