CODE FESTIVAL 2016 Grand Final(Parallel)-A：1D Matching(500)
問題
https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_a
N つの座標 a_i と N つの座標 b_i がある。最短の長さで a_i と b_i をマッチングさせるとき、何通りの方法で最短の長さでマッチングすることができるか。
考え方
未知のものは「マッチングするときの場合の数」である。満たす条件は「最短の長さのマッチング」である。最短の長さであるようなマッチングは、どのような条件を満たすときのマッチング方法になるか知りたい。
これは実験するとわかるが、マッチングさせたときの a_i から b_i への有向辺が逆向きの有向辺と交差している場合は最短長のつなぎ方にならない。
マッチングさせるとき、マッチングすることのできる点が存在する場合はいずれかの点とマッチングする必要があり、その時の選択肢の数が答えになる。
Submission #3468208 - CODE FESTIVAL 2016 Grand Final(Parallel)
ポイント
- 条件を言い換える
