方針
図から格子を座標化する。、、 であり、点 は横道路の途中、すなわち から への1歩の上にある。同様に は から への1歩の上にある。最短経路は右5回、上6回なので、通過条件は必要な部分経路の積、通らない条件は余事象と包除で数える。
解答
図より、 を 、 を とみなす。最短経路では、右へ5回、上へ6回進むだけであるから、全体の道順は 通りである。
(1)
図より である。 から までは右へ1回、上へ2回なので 通りである。 から までは右へ4回、上へ4回なので 通りである。したがって、 を通る道順は 通りである。
(2)
点 は交差点ではなく、横道路の途中にある。図から、 を通るためには、 から へ右に進む1歩を通らなければならない。 から までは右へ2回、上へ3回なので 通りである。その後、 から への1歩は固定される。さらに から までは右へ2回、上へ3回なので 通りである。したがって、 を通る道順は 通りである。よって を通らない道順は 通りである。
(3)
同様に、 を通るためには、 から へ右に進む1歩を通る必要がある。 から までは右へ3回、上へ4回なので 通りである。その後の1歩は固定され、 から までは右へ1回、上へ2回なので 通りである。したがって を通る道順は 通りである。
次に、 と の両方を通る道順を数える。 から までは10通り、 を通る1歩は固定、 から までは上へ1歩だけ、 を通る1歩も固定、 から までは3通りである。よって両方を通る道順は 通りである。
包除原理より、 も も通らない道順は 通りである。
別解
解法2
方針
格子点までの最短経路数を動的計画法で数える。各格子点の値を左と下の和にし、、 に当たる横辺だけ遷移を禁止すれば、余事象や包除を使わず直接答えを得られる。
解答
、 とし、格子点 までの許された最短経路数を とする。通常はである。
(1)
を通る経路は、 から と から を独立に選べるので(2)
は辺 上にある。この辺を禁止し、 の更新時だけ左からの項 を加えずに漸化式を進めると(3)
さらに のある辺 も禁止する。各行を から の順に並べた計算表はとなる。したがって通りである。
総評
難度5、計算量4。 は格子点ではなく横道路の途中にあるため、特定の1辺を通る条件として数える。包除と辺を禁止する動的計画法が同じ362、287を与える。 2解法の最終値を照合し、境界条件・符号・定義域も確認した。
