ICPC 2010 国内予選
結果:
>落選です。
国内13位(学内6位)。解いたのはA,B,C,Dです。
個人的にはEが解けなかったのが痛い。結局間違った方針で実装していたわけで、実力の無さを露呈してます。
まあまだ後3年あるはずなので、(チームを組んでくれる奇特な方がいれば)リベンジするつもりです。
まあまずはTopCoderからだなぁ…ってかさっそく明後日UTPCがあるし！
ちなみに、Javaチャレンジは3位でした。
展開予想を覆して優勝候補のRiPProを下し初戦勝利！そのまま行けるかと思いきや、爆弾(=バグ)が爆発し、準決勝で惨敗。
いや、あのバグが他の試合で発生しなかったことが奇跡なんだけど。(グループリーグで一回発生しただけ。むしろなぜ？)
とりあえず景品が楽しみです！
うちの戦略はミニパンプキンを最速で作れる場所を毎ターン探してそこに移動or魔法陣を書き、ミニパンプキンを作れる場所がなければ相手のパンプキンを壊しに行く、という単純な方法。戦略自体はこれで結構強いのですが、細かな作りこみ(とくにデッドロックの回避とか)で上位のチームとは差をつけられた感じです。
ハル研究所プログラミングコンテスト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個穴に落ちたのでしょうか？)
ハル研究所プログラミングコンテスト2009
ハル研究所のプロコン'09(http://www.hallab.co.jp/progcon/2009/)に参加中。
参加受付＆解答締切は1/8 12:00までなので興味のある方は今からでも？
穴のあるマップ上を、ボールを穴に落ちないように気をつけながら転がしてゴールさせ、その早さを競う、というシンプルな問題なのですが、なかなか難しいです。
とりあえず、この問題の手ごわい点を挙げると、
(1) ボールの位置が実数で与えられる。
(2) ボールの慣性も考慮する。
(3) 制限時間が厳しい。(180秒で1000セットなので実質1セット当たり0.18秒)
(4) メモリ使用量制限。
(5) 外部・標準ライブラリ使用禁止。
これらをどうするか？というところでしょうか。
STL中毒の身としては(5)はなかなか厳しいものです。STLは本当に便利ですよ？
終わったら他の人の解法も聞いてみたいですね。ここにも自分の解法を書いとこうと思います。
コーディングし始めたのが去年の大みそかで正月中ずっとコーディングしてましたが、そろそろアルゴリズムも固まってきて、あとはチューニング、というところです。
