MM 91
WanderingTheCity - Problem:
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16828&pm=14281
WanderingTheCity - Standings:
続きを読む
-
masashinakata
- 1982
- 1
- 0
- 0
-
- いいね！0
hakomo
@hakomof
GUESSのタイミングはyowaさんと同じに確率を求めて85%を超えたら。ただ、あたりはずれにかける係数がChangeProbの推定値ではなく0.1固定（ChangeProbが0.05-0.2の一様分布なのでまあ妥当）
2016-11-12 10:18:56
hakomo
@hakomof
どこをLOOKするかは4マスをLOOKしたときの上位候補の白黒16パターンのかぶりが少ないとこ。かぶりペナルティの重みに候補確率を使ってるとこが強そう。（自分はbest=16, best-1=8, best-2=4...みたく雑というか勾配がゆるすぎたかも）
2016-11-12 10:19:46
hakomo
@hakomof
battyoneさんもwleiteさんも、どのマスをLOOKするか計算するときに、現在地に近いほうから計算して現ベストと歩きコストを元に打ち切り。あと、減点方式で現ベストを下回ったら安全な打ち切り。赤い人々、計算の仕方、順序を工夫した枝刈高速化当然のように仕込んでてすごみ。
2016-11-12 10:21:32
hakomo
@hakomof
GUESSタイミングは確率ベースも一致数の差ベースも大きくは変わらない。ただ計算の仕方的にSに応じた閾値調整を自然に内包して調整が楽なのと、ChangeProbの推定値を自然に組み合わせられる分、確率ベースが少し強そう
2016-11-12 10:32:07
hakomo
@hakomof
ただどっちベースにしても、パーシャルマップの繰り返しがあるかどうかと、パーシャルマップの数に応じた閾値調整はわりと効いたんじゃないかと思ってる（少なくとも10Kくらいは上がると思われ）
2016-11-12 10:37:49