びったんびったん

ユーザビリティ・プログラミングについて。

Yandex Algorithm 2018 Optimization track. Round 2 News freshness

問題文

暫定3位でした。険しい。問題自体はとてもおもしろかった。

greedy

巡回するサイトを1つずつ順番に決めていってパスをgreedyにつくります。パスがつくり途中だと2週目以降にいつどのサイトを訪れるかが定まらずスコアに加味できないので困ります。そこでパスの周期(timeToIndexの和)を決め打ちします。あらかじめ決めた周期(それ以外認めない)になるようにパスをつくることで、つくり途中でも2週目以降のスコアを計算できるようになります。

実装としては、最初は自由にパスを伸ばします。そして周期-150を切ったら、パスの後尾からランダムに伸ばして周期ジャストでパスの先頭に戻れるものの中からgreedyに1つ選ぶなどすると、だいたい成功します。

評価関数は、testerスコアの期待値 / すべてのパスのtimeToIndexの和としました。すべてのパスのtimeToIndexの和でわることで、timeToIndexあたりのスコアが高い効率のよいサイトが選ばれていきます。

あとはテキトーな周期で何回かgreedyしてmaxをとれば8600点以上が出ました。

周期

周期についていろいろ。

timeToIndexあたりのスコアがよいサイトばかりを選ぶとtimeToIndexが小さいので周期が短くなります。しかし周期が長いと週回数が少なくなり、1つのクローリングが影響する箇所が少なくなるのでよいスコアを得やすいです。短いことにも長いことにもメリットがあるので周期には短すぎず長すぎないベターな長さが存在します(実験によって確認)。

ベターな周期はすべてのサイトのtimeToIndexの和の45%-70%(5000-20000)ぐらいになるようです。またパス長は周期を長くするためにNギリギリであることが理想的ですがgreedyによって得られるパス長はNの65%-100%くらいになります。

ほどよい周期のパスをgreedyで得るために評価関数をtesterスコアの期待値 / pow(すべてのパスのtimeToIndexの和, timeCoef)に変えます。timeCoefが1に近いほど周期が短く、0に近いほど長くなります。timeCoefのよさげな値は3分探索で求めることができますがgreedy1回がとても重いのでやめました。timeCoefのよさげな値をローカルで時間をかけて求めて、testcaseパラメータと最小二乗法でえいっしたらこんな式に、

timeCoef = sqrt(S / (double)numberOfEdges) * -7.836528104606689 + 0.7974926014955707;

timeCoefは決まりましたが、そのtimeCoefに対応する周期は事前にわかりません。周期が長すぎるとパス長制限で構築に失敗しますし、短いほどスコアが悪くなります。なので2分探索で構築に失敗しない最大の周期を求めます。

ここまででよさげな周期を求めることができました。これで8700点ぐらい

周期には他にも着眼点があって、周期がtopicのfreqの倍数のときスコアがよくなります。というのも、そうであるときニュースの生成周期とクローリングの周期がそろうので、1週目で高スコアをとれれば、すべての周回で高スコア(同スコア)をとれるためです 。周期がずれてるとすべての周回で高スコアをとるのは難しくなります。

なのでいずれかのtopicのfreqの倍数であるような周期の中から2分探索すると8740点ぐらい

山登り

この問題はぱっと見山登り/焼きなましできない系に見えますができます。

timeToIndexの和が110程度の部分パスをランダムに選びます。そしてtimeToIndexの和が同じであるようにランダムに生成した部分パスと置換します。こういう近傍だと変更域以外の時間がずれないので山登り/焼きなましが有効ななだらかに近い探索空間になります。

greedyの結果を山登りして8790点ぐらい