方針
図からA、Bと通行止め2辺の座標を読み取る。(2)は積の法則、(3)は2つの禁止辺を通る経路を包除原理で除く。
解答
(1)
から へは東へ6回、北へ4回進むので通りである。
(2)
図2では 、 である。したがってよって をともに通る経路は通りである。
(3)
通行止め を通る経路は通りである。通行止め は の北向きの辺であるから、これを通る経路は通りである。両方を通る経路は通りである。包除原理によりしたがって 通りである。
別解
解法2
方針
格子点ごとの到達数を漸化的に記入し、2本の通行止めに対応する寄与だけを除外する。
解答
(1)
各格子点の経路数を、西隣と南隣の値の和として順に記入する。通行止めがないとき の値は となる。
(2)
までの経路数は2、 は1、 から までは35である。よって(3)
辺 と辺 からの寄与だけを加えずに動的計画法を行うととなる。右上の値より答えは 通りである。
総評
難度5、計算量4、目安18分。原図から 、禁止辺 を再読した。答えは 。既存の60、98は図の読み違いで、包除原理と動的計画法の双方により訂正した。


