Google Code Jam Qualification Round 2019:You Can Go Your Own Way
問題
codingcompetitions.withgoogle.com
N * N マスを左上から右下まで移動する手順が与えられる.この手順のパスを通らずに右か下への移動だけを用いて左上から右下まで移動する手順を1 つ出力する問題.なお,入力で与えられるパスと交わることは許される.
解法
与えられるパスが下に移動したら右へ移動し,右に移動したら左へ移動すればいい.こうすることで,2つのパスが交わることはあっても重なることはない.O(|P|).
解答