ハル研究所プログラミングコンテスト2009 結果など
ハル研プロコンは結局学生部門5位(総合6位)でした。微妙。
アルゴリズム
(1)穴の4頂点の少し外側などをノードとしてとり、ダイクストラで経路を求める。
(2)１で求めた経路の周りを塗る。
(3)２で塗ったところの中で、0.5きざみの方眼状にノードをとり、ダイクストラで経路を求める。
というダイクストラに頼りっきりなアルゴリズムです。
計算で曲線を出すアルゴリズムの人もいたそうですが、そんな甲斐性はありませんでしたw
考え方
このアルゴリズムの肝であり、同時に弱点でもあるのは、
「加速度を東西南北4方向,大きさ0.4に限定し、速度が4より大きくなるような加速を許さなければ、ボールは0.5きざみの方眼の目の上を移動する」
という単純化を行ったことです。
これと、(1),(2)での範囲限定、穴の中にある点の除外により、ボールの状態(位置x速度)を少なくし、制限時間に収まる範囲内でダイクストラをできるようになっています。
ただ、可視化プログラムでみるとわかるのですが、このプログラムで出した解答はやたら東西南北方向の直線の上を動きたがります。なぜなら、単純化の影響で、東西南北なら速度最大4で動けますが、斜めだと速度が最大で3.8程しか出ないからです。
斜めに動くのが多いステージでは、この.2の積み重ねはでかい。
最後は、速度が4より大きくなるような加速を許し、そういう場合の位置と速度を大雑把に扱う、という方法で斜め移動の壁を越そうとしましたが、得点の向上にはつながりませんでした。(手元では上がったのですが、サーバ上では下がってしまいました…誤差の影響で2,3個穴に落ちたのでしょうか？)
