参加しながら考えたことの源泉かけ流し。
問題文はこちら
1日目
所感
問題読んだ！めっちゃおもしろそう！！
モンテカルロかなぁ？モンテカルロだろなぁ。
制限時間 60sec が長すぎてやや萎えてる。やるけど。
ローカルでのテストでは 20sec とかで回すかなぁ。
サンプルが invalid な出力をしててンモーとなる。
いつもより provisional test のテストケースが少ないので、オーバーフィッティングに気をつけないとなと思った。
やったこと
とりあえずサンプルみたいに N 分割して、残ったやつを N 分割して…というのを試験紙がなくなるまでやるやつを書いた。
手元で 100 ケース回して平均取ってスコア 192986 だったので提出すると 124340 になった。しょっぱい。
300 ケース回しても平均 176118 なので、本番スコアをあてにするのは本当に危なそう。
2日目
花金で深夜まで飲んでた。
3日目
「各試験紙に i 本のワインをアサインする」を全通り試すやつを書いた。
それぞれの手の評価は、深さ 1 のモンテカルロをしてみて毒なしが確定するワインの本数。
→ 本番では 140k くらいな手応え。
これでちょうど真ん中くらいの順位。
もうちょっと上でも良いのにと思っちゃうので、何かを見落としてる気がする？
→ 各検定ごとにランダムにワインをアサインするようにした（今までは順番に振ってた）ら 10k ほど伸びた。150k くらいの手応え。
4日目
手元 100 ケースの平均が 235k なのに本番 148k だったので、本番は完答できるケースが少ないということ？
（それにしても剥離しすぎている気もするが…）
この状況で他人に負けてるってことは、毒の特定が難しいケースが苦手なんだろうなぁ、きっと。
前回の検定の結果からそのワインが毒である確率っぽい値を計算し、その値が小さいほど検定時アサインされやすいようにしたら手元でも本番でも 10k ほど伸びた。
5日目
モンテカルロなのは外してないと思うんだけど、1ターン先までしか見ないのが良くないのかなぁ。
ということで、最後までプレイアウトさせてみようか。
→あんまり伸びなかった。次の手の選び方を完全にランダムにするといくらなんでもスコアがぼやけすぎている気がする。
これは明日の自分に任せるんですが、残り瓶数 × 残りラウンド数 × 残り試験紙数 とかで DP っぽいことできないかなぁ。
6日目
TL を見てる感じやっぱり本番スコア異常に低くなるようだ。良かった。
昨日の DP のやつ、実装してみたけど何か微妙にバグる。
numBottles:8592 testStrips:7 testRounds:2 numPoison:158 に対して初手で各試験紙に 134 個のワインをアサインして全滅はさすがにおかしい…。
→試行回数が少ないだけでした。
回してみると意外と重くて 60sec で足りないケースあるなこれと思ったら、残り瓶数(10000) × 残りラウンド数(10) × 残り試験紙数(20) × 各試験紙にアサインするワイン数(150) × 試行回数(100) × 毒の数(500) でそりゃ重いよなって感じ。
精度多少下がってもいいので(シミュレーションで使ってる)毒の数だけでも削りたいところ。
7日目
毒の数をサボってだいぶ速くなり、ようやくまともに運用できるかなってなってきたんだけど、スコアがふるわず。
メモ化再帰風の実装で、見る深さを深くしていくほどスコアが下がる…。
話は変わるけど、シロと確定する個数の期待値を最大化してるので、ちゃんとスコアに合わせた方が良いかもしれない。TODO。
あとね、6 0 s e c は 長 い ！ ！ ！
ローカルでのテスト、終わらん！！
8,9日目
4 日目から一向にスコアが伸びない。
10日目
よくわからなくなってきたので、とりあえず testRound が 1 の場合に絞って厳密にモンテカルロしてみてる。
各試験紙に均等にボトルを割り振るとすると、numBottles:9021 testStrips:6 numPoison:54（167 本に 1 本が毒）の場合でも 201 本ずつ割り振るのが最適（平均 1.87 枚無毒判定する）って言われちゃうんだよなぁ。直感に反するなぁ。
何はともあれ、これで 1 割のケースはベストを尽くせているはず。
均等に割り振らないケースが最善なら話は別だけど…。
TL で線形探索を三分探索にしたらだいぶ速くなったというのを見かけて、ボトルに割り振る本数については三分探索で OK だなぁと思った。ふーむ。
…これ、めちゃくちゃ速くなるのでは！？
11日目
各試験紙に割り振るワインの数を黄金分割探索するようにしたらめっちゃはやくなった！
これにより 2 ターン先貪欲ができるようになったんだけど、スコアは伸びず…。
12日目
スコアが伸びないの、モンテカルロによるスコア推測＋黄金分割探索するところで探索範囲が変になっちゃってたのが一因のようだ。
根本的な解決策は試行数を増やすことなんだけど、計算時間的に怪しいので探索時の最大値の初期値を小さめにすることで対応した。
具体的には、high = min(ボトル数 / 試験紙数 + 2 くらい, 1.5 * ボトル数 / 毒ワイン数) からスタートにした。
（というか、試行数増やすとスコア下がる…。うーん？）
→ DP テーブルからスコアを読み取ってるつもりが、最善手のワイン数/試験紙の値を読み取ってスコアとして使ってた。
そりゃ試行回数増やせばバグが顕著になるよね。
→ バグらせてる方がスコアが良い…えぇ…？
一応 500 ケース試してるんだけど、(本番換算で) 7000 点くらいの差が出る。
2 ～ 3 ターン先の最善手でたくさんのワインをアサインするような手を選べということ？分からん。
依然として本番のスコアは 4 日目のを更新できてないけど、手元 500 ケースだと 4000 点伸びてるので進捗はなくはない。割には合わないけど。
デバッグ出力を眺めていたのだけど、ボトル数 6676, 毒数 75, 残りターン数 1, 試験紙数 1 で最善手 ボトル数/試験紙 = 111, 白確定ボトル数期待値 55.5 は明らかにおかしい。
これは明らかにバグってる。よかった！改善のしようがある！
→試行回数が少ないだけでした。天丼かよ。
13日目
本番スコアがローカルより低いということは、本番ではハイスコアを取れるケースが少ないということ？
で、本番スコアだと4日目のコードが今のコードより 10k 点くらい高いのにローカルではどっこいどっこいということは、4日目のコードはハイスコアが取れないケースにつよいということ？
だとすると、ハイスコア取れそうにないときは4日目のコードに切り替えれるってのをやるとスコア伸びるのでは？
→まぼろし～～～～
MM みたいにクラスにまとめて書いてると戦略の切り替えめっちゃ楽だなって思った。（小並感）
14日目
ローカルではそんなスコア変わってないんだけど、出してみたら 160k 出たので満足。
みんなシステスでどれだけ上がるんだろうなぁ。
まとめ
↓↓↓こちらを見よう↓↓↓
togetter.com
いつもお世話になっています🙏🙏🙏
