Mujin Programming Challenge 2017 A Robot Racing

N(1≦N≦100000)体のロボットがそれぞれ座標x[i]≧0にいる。これらの任意のロボットを左に1または2移動させる(飛び越えられる)とき、ゴール(座標が負)する順番は何通りあるか？

言葉で説明するのが難しいアルゴリズム。右から順に調べていって、今調べているロボットが次のような形になっているかを確認する。

o_o_o_ox

o:他のロボット

x:調べてる途中のロボット

_:空白

こういうロボットのゴール順は5通り、かつこれより左にあるロボットは絶対に今調べているロボットを追い越せない。なので、現在の組み合わせに5を乗じ、このロボットを除去する。飛び飛びの場合はそのまま放置する。

こういったものを全部除去した結果、ロボットの配置は以下のようになる

o_o_o_o___o__o____o__o

o: ロボット

_:空白

こういう状態になったら残りのゴール順は自由のなので、(残りのロボット数)！を乗じて答えになる。

アルゴリズム忘備録