GCJ Round 3

500人通過中117位で通過。

D small

典型的DP

C small

N <= 10で配置は1個前の列がどう埋められているかにしかよらないのでM *2^Nだけの状態に関してDP

B small , large

(現在地 * 扉1の配置 * 扉2の配置)の状態空間に関して幅優先する。扉の位置が一つの壁に関して4通りあるとか銃を撃つときにはターンを消費しないと色々と条件があり、実装にかなり手間取った。あとlargeはメモリが足りなかったりしてその場でintの配列をbooleanの配列に直すとかをしてかなりあせった。実際は扉2は撃ったらすぐ入ると考えたら状態空間は(現在地 * 扉1の配置)だけでいい気がする。