方針
図の格子点を座標で正確に読み、(1)は東西移動の並べ替え、(2)は区間ごとの積、(3)は全体から通行止めの1辺を通る経路を引く。
解答
(1)
から へは東へ6回、北へ4回進む。10回の移動のうち北へ進む4回を選ぶので、通りである。
(2)
図2の格子点を 、 と読むとである。したがって積の法則より、 をともに通る経路は通りである。
(3)
通行止め は から へ向かう東向きの1辺である。この辺を通る経路は通りである。よって、通行止めを避ける経路は通りである。
別解
解法2
方針
格子点ごとの到達数を西隣と南隣の和で更新する。通行止めの辺から来る寄与だけを加えない。
解答
(1)
各格子点に「そこへ到達する経路数」を書く。西隣と南隣からしか来られないので、通常の格子点では両者の和を記入する。南端・西端を1から始めて右上まで計算するととなり、 の値は である。
(2)
同じ表で の値は である。 は1通りで、 から までの小格子の経路数は3である。よって(3)
の寄与だけを加えず、同じ漸化式を続けるとを得る。したがって答えは 通りである。
総評
難度4、計算量3、目安15分。原図の座標を再照合し、答えは 。既存解答の(2)の60通りは図2のA、Bの位置の読み違いであり訂正した。二項係数と動的計画法が一致する。


