きろく

特筆すべき記録のまとめ

Mujin Programming Challenge 2018 : C - 右折

問題

C - 右折

N 行 M 列のマス目が,障害物と通路の2つの要素で構成されている.ロボットは通路マスのどれかから4方のどれかの方向に向かって1マス以上進む.その後,右に方向を変え,1マス以上進む.このとき,ロボットの進み方の通り数を求める問題.

解法

方向転換するマスを固定して考える.方向転換するマスを1つに定めると,そのマスから上下左右に最大何マス通路が続いているかを求めたい.これが求まれば,簡単な四則演算でそのマスを方向転換するマスとするロボットの動き方の通り数が求まるので,これを全ての通路マスについて同様に計算をすればよい.

肝心などれだけ通路マスが続いているかを求める方法は,行・列ごとに障害物のマスの y,x 座標を vector に入れて置き,それぞれの vector をソートし,方向転換するマスを決めた際に二分探索によって最も近い障害物マスを求め,座標の差から求める.

これらの方法をとると O(NMlogNM) になり間に合う.けれど,解説は O(NM) だった.

解答

Submission #3018309 - Mujin Programming Challenge 2018

f:id:babcs2035:20180817083627p:plain

gist.github.com