第18回日本情報オリンピック　予選２

2018年12月10日
情報オリンピック日本委員会

解説

駒の座標を配列で管理し，動きを 1 回ずつシミュレートをする． 移動元がゴールマスでないかは O(1) 時間で判定できる． 移動先の座標に駒があるかどうかは，残りの駒の座標をすべて見ることで，O(N) 時間で判定できる． よってこの問題は O(NM) 時間で解ける．

この問題ではこれ以上の高速化は要求されていないが，駒の座標が常に昇順であることを利用すると，移動先の座標に駒があるかどうかが O(1) 時間で判定でき，全体で O(N+M) 時間でこの問題は解ける．