問題概要

N 個のチームがサッカーの総あたり戦を行う。1 試合ごとに勝てば W 点、引き分けだと D 点、負ければ 0 点のポイントを獲得する。各チームには固有の隠しパラメータである攻撃力・防御力が設定されており、各試合では自チーム・相手チームのパラメータ（と、得点の分散具合に係るテストケース固有のパラメータ X）に依存してランダムに得点 (0~3) が定まり、得点の多いチームが勝利となる。

入力として、各チームの総得点数、総失点数、総獲得ポイント数、およびパラメータ W, D, X が与えられる。各チームが各試合で得た得点を推定せよ。

全文はこちら。

解法

解法は大きく 2 つのフェーズに分かれる。

隠しパラメータを推定するフェーズ
推定した隠しパラメータを基に各試合の得点を推定するフェーズ

隠しパラメータの推定

基本的な方針は以下の通り。

各チームに適当な攻撃力・防御力を割り振る。
いずれかのチームの攻撃力 or 防御力を +1 or -1 する。
総あたり戦のシミュレーションを行い、入力値とのズレを計算する。
+1 or -1 する前のズレの値と比較を行い、改善されていれば +1 or -1 の操作をそのまま採用、悪化していれば +1 or -1 の操作を取り消す。
2.~4. を十分な回数繰り返す。

シミュレーションでは、攻撃力・防御力の値より各チームの得点の合計 / 失点の合計の期待値が正確に求まるため、その期待値と入力値との差の絶対値の和をズレの値として用いた。6 日目くらいまで愚直シミュレーションでのモンテカルロをやってたのは内緒。
ポイントのズレはノイズになるので無視した。

2.~4. の操作は各チーム 30 回ずつ行った。総処理時間は N = 50 でも 100ms 程度。

次のテーブルは seed=6 (N=12, X=6) での隠しパラメータの推定値及び実際の値。まぁぼちぼちの精度。

   | estimate |  actual  |
---+----------+----------+
0  | (10, 5)  | (10, 6)  |
1  | (10, 2)  | (9, 3)   |
2  | (2, 4)   | (2, 3)   |
3  | (2, 7)   | (2, 8)   |
4  | (6, 4)   | (5, 4)   |
5  | (4, 6)   | (4, 6)   |
6  | (6, 8)   | (7, 9)   |
7  | (7, 2)   | (7, 2)   |
8  | (6, 2)   | (7, 1)   |
9  | (8, 9)   | (8, 9)   |
10 | (8, 9)   | (9, 7)   |
11 | (6, 5)   | (6, 5)   |

X = 2 の場合はシミュレーション時のみ X = 1 として期待値を計算した方が最終的なスコアが良くなった。なんでだろう。

各試合の得点の推定

N および X の値によって方針を変えた。

X > 2 or (X == 2 and N <= 20) の場合

出力する得点表は、入力の総得点・総失点・総ポイント数とのズレが小さい方が好ましい。ただし、いくらズレが小さいからといって、前フェーズで推定した隠しパラメータからはとても導出されないであろう得点表を選んでしまうと、実際の試合結果とはかけ離れたものになってしまう。

なので、 出力する得点表と入力値のズレ に log(試合結果が出力する得点表どおりになる確率) の絶対値を足した値を最小化する焼きなましをやった。いずれの値も差分計算が可能なので高速にイテレーションを回せる。

N の値によってどちらの値をどれだけ優先すべきかが変わってくるので、よしなに係数を掛けてあげる。

double keisu;
if (N < 10) keisu = 0.5;
else if (N < 15) keisu = 1;
else if (N <= 20) keisu = 2;
else if (N <= 30) keisu = 3;
else if (N <= 40) keisu = 5;
else keisu = 7;

int nowDiff = calcDiff(teams);
double nowProbLog = calcWholeProbLog(scoreTable);
double nowValue = nowDiff - keisu * nowProbLog;

また、ここでの得点表と入力値のズレの計算では、隠しパラメータの推定では無視していた総獲得ポイントのズレも用いる。

なぜ X > 2 or (X == 2 and N <= 20) ？

上の条件を満たさない場合だと、最終スコアが安定しなかった。Actual な得点のばらつきが大きいので、今回の焼きなましで用いた目的関数にはマッチしなかったのかもしれない。

X == 1 or (X == 2 and N > 20) の場合

まず各試合について、i 点の得点を得られる確率を p_i としたとき、p_i が最大となる i を得点として採用した。なぜ期待値でなくこの値を使ったかというと、使ってみたら最終スコアが伸びたからなのだが、理由はよく分からず…。期待値を使うと得点の推定値が丸くなるが、真のスコアや勝敗を当てないことには 0 点なので、丸くする意義がない？

上の処理の後、得点を +1 or -1 してみて入力値とのズレが小さくなるところがあれば貪欲に +1 or -1 する。

やり残したこと

ないです。

結果

暫定 11 位 / 57 人でした。
ただ割とスコアブレ得る問題な気がするので、上揺れして 10 位になってくれ！

iwashi31’s diary

TopCoder Marathon Match 121 "SoccerTournament"