ハル研究所プログラミングコンテスト2012

ハル研究所プログラミングコンテスト2012に参加しました。
応募締め切り時は総合9位でした。（最後に最適解が出ないコードを出してしまって少し不安、最大スコアのコードで順位付けてくれるんだろうか）

どのような方針を取ったか書いていきます。

まず、問題の制約を愚直に列挙すると

• 1 <= W, H <= 24
• 周期210
• アイテムの状態数6
• waitしたか

探索することを考えると、状態空間のサイズはO(W*H*210*6*2)で、普通に競プロでもでそうな制約です。競技やってる人ならすぐに方針が見えたと思います。

初めに取ったアプローチはdjikstraです。状態を(座標, 周期, アイテムの状態, waitしたか)として、コストはソースコードにあったスコア計算のマイナスになる部分を使いました。
ただし、このままではサーバで20secに間に合わないので、A*を使います。ヒューリスティックス関数には針を無視したゴールからの距離を用います。これでジャッジサーバで19secほどでました。

最適解が出るようになったので、stage数を10^6ほどにしてPCを温めます。
その結果わかったことは、最適解の場合はdamageを一度も受けない、waitはしないです。
これから、状態のwaitしたかを省けます。探索時にdamageを受ける場合はそれ以降探索する必要がありません。

最終的な方針は、状態を(座標, 周期, アイテムの状態)。コストは針を無視した最短路から外れた回数としました。具体的なコストは最短路に沿って移動した場合に0, アイテムを使った場合に1, 最短路から外れた場合に2となります。
コストが0~2だけなので、priority_queueを使わずに、queue q[コスト];のように複数のキューを用意しました。小さいコストのキューから見ていき、空になったらコスト+1のキューに進みます。なので、コード的にはbfsっぽい感じになっています。（考え方的にはA*と一緒です）

その他高速化のためにしたこと
キューにつっこむ状態は32bitに詰める
コストなどを格納しておくテーブルはint -> charにする
テーブル配列の次元をできるだけ下げる。例えば、table[y][x] -> table[1024]として、table[(y << 5) | x]でアクセスする

一番速かった実行時間は3.29secでした。自分のチューニング力だとこの辺が限界です。
この方針で一番ネックになっていたのは、周期の状態数が大きいことでしたが、自分で解決案が出せませんでした。
トップ層の人たちは状態を(座標, アイテムの状態, コスト)として、状態の値を各周期で到達可能かを持つ方針みたいです。