Educational DP Contest / DP まとめコンテスト Y - Grid 2
解法
包除原理を用いて解きます。
個以上の壁を通り、番目の壁に到達するような通り方の場合の数
とします。ここで、壁について、行、列の順で昇順ソートしておくと、番目の壁を通る際に、番目以降の壁を先に通ることはありえなくなるので、うまく計算することができます。
また、スタート地点を番目の壁、ゴール地点を番目の壁、とすることで、初期化はとすることができます。
ただし、
は、初めにソートしたときに満たすようになっています。
右側のコンビネーションの項は、番目の壁から番目の壁に行く行き方です。
これを計算すると、答えが
となるので、のの部分を、の2通りに集約することができます。こうすることで、計算量がにおさまり、
になります。
感想
包除原理は普段解けないことが多いのですが、割とスッキリ解けたのでよかったです。