Topcoder Marathon Match 99
作成日：2018.03.26
カテゴリー：競プロ 参戦記録
目次
- 1日目(2018.03.15)
- 2日目(2018.03.16)
- 3日目(2018.03.17)
- 4日目(2018.03.18)
- 5日目(2018.03.19)
- 6日目以降(2018.03.20-)
- 結果
- 振り返り
1日目(2018.03.15)
問題文を読む。上手い戦略を考えるのが重要である問題のようだ。
期待値を精度良く計算したり、分散を用いて確率的な挙動をしたりすることになりそうだ。
今回はテスターやビジュアライザーはないようだ。
しかしローカルで色々試したいのでテスターを作ることにする。
フォーラムにJavaのプログラムがあったが、使い方がよく分からなかったのでC++で書き直す。
2日目(2018.03.16)
本体の実装に着手する。
とりあえず1回のnotePlayから得られる情報を元に簡易的な方法で期待値を求め、一番良かったものをquickPlayすることにする。
ただ期待値が$1.0$以下となる時は損をするのでquickPlayを行わないようにする。
手元で実行した結果を比較することになるので基準を考える。
相対スコアで評価されるので、初めのコインと最後のコインの比の平均を基準にすると良さそうである。
しかし中には比が$30$を超えるものがあったので、上位$10\%$は無視することにする。
また、比の中央値も確認することにする。
この基準を用いて先のプログラムを評価すると、平均$0.888$、中央値$0.952$であるから、スロットをやらない方が良いということになる。
1回試しただけだと、本当は期待値が悪いのにたまたま良い表示を得られてしまうことがある。
そこで、何回か繰り返してそれぞれで期待値を求め、その期待値の平均が良かったものを採用するようにする。
quickPlayをやる時間が無くなってしまっては意味がないので、繰り返す回数は最大でもmaxTimeの半分までとする。
色々試したところ、平均$1.264$、中央値$1.227$となる。
順位表を見ると、何人か同じ点数になっている部分がある。
これは恐らくスロットを一回もしないプログラムだと思われる。
この点数と$1$位の点数の比が$1.5$ほどであったから、手元で平均$1.5$を出すのが目標となりそうだ。
3日目(2018.03.17)
2回のnotePlayの結果を組み合わせて期待値を求めることにする。
2個の結果の組はスロットを行った回数の二乗のオーダーで得られる。
色々試したところ、$24$回ずつnotePlayを行うのが良いようだ。
これは平均$1.373$、中央値$1.263$である。
そろそろ提出しようと思い、提出すると$466581.66$点の$66$位となる。
これは何もしないプログラムを提出したと思われる人たちの$559319.50$点、$47$位よりも低い。
評価基準が悪いと思い、一番良い機械の期待値とプログラムが選んだ機械の期待値の比(以下、正確性とする)を求めてみることにした。
するとこのプログラムでは$87.87\%$となる一方、何もしない、すなわち期待値が$1.0$である時は$62.05\%$となる。
これでは提出結果と合わない。
問題文をよく見ると、コインが足りないのにquickPlayを呼び出してはいけないと書いてある。
今のプログラムはこれに違反していたので、それを直す。
さらにnotePlayを$5$回ずつできない時は何もしない等の変更を加えて提出すると$782082.14$点の$17$位となる。
4日目(2018.03.18)
より多くのnotePlayの結果を組み合わせた方が精度が出るだろうから実装する。
$5$回の結果を用いると平均$1.400$、中央値$1.307$、正確性$87.04\%$となる。
正確性は下がった一方で平均や中央値が改善したのは、notePlayの回数が減った分quickPlayの回数が増えたためと考えられる。
これを提出すると$794040.67$点の$16$位となる。
wheel sizeごとに分けて平均を取ると平均$1.403$、中央値$1.323$、正確性$88.35\%$となりなぜか改善したので提出すると$803630.29$の$15$位となる。
期待値を求める部分の計算量を改善してnotePlay$6$回分の結果を用いたものを実行してみたが、平均$1.320$、中央値$1.292$、正確性$87.45\%$となる。
多くの情報を用いた方が良くなると思っていたので、この結果は不思議である。
notePlayを$5$回として実行すると計算量改善前と同じ結果が得られたので、プログラムの間違いではないようだ。
notePlayの回数が増えてquickPlayの回数が減ったことで悪くなったのだろうか。
期待値の計算の仕方が間違っているのだろうか。
それとも単に誤差の範囲だろうか。
5日目(2018.03.19)
行き詰ったので、notePlayで得られた出目をそのままwheelだとみなして期待値を計算してみることにする。
すると平均$1.363$、中央値$1.324$、正確性$92.33\%$となり改善が見られる。
これを提出すると$818664.56$点の$16$位となる。
前のバージョンをいじっていると平均$1.400$、中央値$1.292$、正確性$88.28\%$という結果が出る。
一応提出してみると$802226.35$点の$23$位となる。
悪くなったので前のものを提出し直して$818544.35$点の$19$位となる。
maxTimeが少ないとnotePlayを十分な回数行うことができず正確性が悪くなる。
そこでnotePlayをそれほど行えない時は前のバージョンで期待値を計算することにする。
これは平均$1.415$、中央値$1.346$、正確性$92.89\%$となったので提出すると$813572.62$点の$21$位となる。
この程度の増減は誤差の範囲なのだろうか。
6日目以降(2018.03.20-)
$100$ケースのテストでは結果が誤差の範囲に入ってしまい性能を上手く評価できないと思ったので、$1000$ケースでテストすることにする。
これまで提出したコードを確かめると、最も直近に提出したものの平均$1.368$、中央値$1.241$、正確性$90.14\%$が一番良いという結果が出る。
ただ、そのコードでも一番良い機械を選んでいるテストケースの数は$584$個と$6$割を下回っている。
そこで期待値に応じてquickPlayを行う回数に重みを付けてみることにする。
色々試したところ、$exp$(([期待値]$-1.0$)$\times 15.0$)に確率を比例させると平均$1.367$、中央値$1.257$となることが分かる。
これを提出すると$813865.07$点の$20$位となる。
他の箇所のパラメータを変えると平均$1.384$、中央値$1.251$となる。
これを提出すると$809972.19$点の$26$位となる。
$100$ケースでのテストであるから、スコアが下がったことは気にしない。
結果
システムテスト前は$809307.63$点で$34$位。
解法は初めにnotePlayを$20$回行い、そこで得られた出目をwheelとして期待値を求める。
そして期待値に応じて重みを付け、quickPlayを行う。
但しnotePlayやquickPlayを十分な回数行うことができない場合は何もしない。
振り返り
2,3日目に試したことは4日目に試したことの下位互換であるから、2日間は無駄とまでは言えないかもしれないが後にあまり利いてこないことをしていたと言える。
アイデアを小出しにしても得しないので、思いついたことはすぐに試すべきであろう。
＜(古い記事)
関連
Topcoder Marathon Match 99 最終結果 (新しい記事)＞