HACK TO THE FUTURE 2018予選

更新日時:

HACK TO THE FUTURE 2018予選

ソースコード

解法のメモ

A - 山型足し算

97 億点しか取れなくて、そこから先からどうするかやる気なくして FGO やっていた。

chokudai さんの解説放送を聞く。

46 億点は $Q = 0$ を出せば良い。 96 億点はランダムでできる。 97 億点は、貪欲法でできる。 98 億点は、「超えない」ではなく「できるだけ高い点数」の貪欲法でいける。

ランダムと貪欲を組み合わせると多少マシになる。半分ランダムでやって、貪欲をやる。これで 99 億 8000 万点くらいまでいけるという。生成がランダムなので、中央について山形になる。ランダムでやると中央について山形になる。つまり差がべったりになる。ここから貪欲にするとうまくいく。

山をずらす場合、差分計算をすると、 $+1$ の領域と $-1$ の領域にざっと分かれる。区間を小さくするのは全区間に $-1$ をすることに対応する。この改良をする。山登り法をちゃんと実装し高速化もすると 99 億 9700 万点になる。高速化する際には累積和を使う。更新する時だけ累積和を更新する。

焼きなまし法で、だんだん悪い方向への移動確率を下げていく。 99 億 9800 万点までいけるらしい。 99 億 9900 万点までいけるかもしれないとのことだった。

Q: 遷移はどのくらいがいいか? A:よほどのことがない限り最小単位で動かす。遷移の種類を増やすといい。

これが解説でした。

決勝のオープンコンテストもあるよ! 終わり。

その他

うーん、ずらすのは最後にやればよかったのか。

コメントする