AtCoder Heuristic Contest 002 に参加しました。
方針
マラソンに興味はあったのですが、特にアルゴリズムの学習とかは進められて居なかったので、伝家の宝刀卍貪欲法卍である程度乗り切るつもりでした。
問題文を見ると、超簡単な貪欲として、4方のタイルの中で、まだ訪れてない方向かつ最も大きいスコアを得られる所に進むのが思いつきます。
まずは一回それを実装してA... WA あれ？
よくよく見るとsx、syは0~49なのにsx--、sy--してました。
次に思いついたのは、現在地から一定回数貪欲法を繰り返して、どれだけの回数進めたかをしてみて、4方向の中で最も移動回数が多い方向に進む方法です。
ただ50×50なので、毎回最期進めなくなるまで行動させても処理がすぐ終わり、スコアもそんなにだったのでもう少し考えました。
次は現在地から、一定回数は無条件に四方への移動を全探索、その後は最初の貪欲法で進んで、最終的に移動回数が多かった物を選んでその方向に進む方法です。
この全探索回数は、コードテストで回してみた結果17回がギリギリっぽかったです。
その後の時間は、全探索後のピックする方向の評価関数作りに勤しんでいました。
移動回数のみ、得られる点数の総和のみ、移動回数と得られる点数の総和を重み付けしたりしました。
最終的には、だいたい 移動回数:総和 が 1: 50 になり、 実験結果から移動回数に下駄を大きめに履かせたかったので 移動回数*300 + 総和 を使いました。
結果
