解法
高橋君が動かない、という操作を選択した場合、青木君は動かない、という操作を行ってゲームを終了させればよいので、高橋君が駒を動かさない、という選択肢は存在しません。
よって、高橋君が動けなくなるように青木君がうまく動けばよいです。
駒が列目にある際にゲームが終了すると仮定します。
青木君は、回、どこかで移動を行うことになります。
このときに青木君はどのタイミングで移動を行えばよいか？を考えます。
ゲームが終了するのは、という障害物が存在する場合で、かつ
に駒を動かすことができるときです。
この際に高橋君が行う操作の回数は、回です。
ということで、高橋君が行う操作の回数は、ストップする障害物の位置のみに依存し、青木君がどのような行動をとるか、には依存しません。
なので、できるだけ上の行に存在する障害物でストップさせたいので、極力はやく、列目に移動することが最適になります。
ということで、列目でストップする際は、
高橋君:常に移動する
青木君:
列目より左に居た場合、右に障害物がなければ移動する、そうでなければ移動しない
という操作が最適になります。
あとは、列目でストップする場合の回数を全ての列について計算すればよいです。
列目に移動したときに何行目にいるか、というのは愚直にシミュレートすればよいです。
感想
すらすらと考察できたので、あとは実装スピードです。
