ゴールデンウィークなんて、わかってたけど、あっという間だったな。というわけで楽しく問題解いていこう。今回は、ちょっと亜流な解法で。
問題
解説
ありがちな最短経路問題の中で、全体の形が四角じゃない問題。そんなこと無視して、↑に４回、→に３回行けばいいのね、なんてやってはいけない。連続↑に４回とか行けないわけだから、単純に矢印並べではパターンを洗い出せない。
じゃどうするのかというと、原点に戻って考えてみる。必殺技が使えないときには、普通にパンチ・キックで敵に挑むわけだ。場合の数の原点は、丁寧に数えること。このとき、愛言葉は、もれなく、ダブりなく。カッコ良くいえば、MECEとなる。
基本姿勢は、この「もれなく、ダブりなく」（MECE）で、そこから楽をするべく、効率的な数え方を模索していくことになる。
Aを出発して指でなぞりながらBにたどり着く経路を数えるという、長地道な作業をどう効率化できるだろうか。
いくつか解法・考え方はあるけど、まずはシンプルに考えてみる。東に2回連続いかない条件は、否定条件ゆえ、一旦肯定状態である2回連続して東に進む状況を算出し、最後に引くことにしよう。さて、どんな仕組みで各場合は増えていくのだろう。
どれでもいいから、ひとつ経路を取り上げてみる。その経路のどこかの交点で、違う選択肢をとれば、別のパターンが生まれる。つまり、交点がパターンを増やすきっかけになっていると解釈できる。
じゃ、一般に交点でどのようにパターンが増えるのかを考察してみよう。最も単純化したケースからはじめる。最も単純化したケースとは、BをAから一歩目の地点においた場合のものだ。
ここから便宜的に、東方向と北方向にそれぞれ進んだ点を（東、北）と表すことにする。
そうすると、単純化したケースは（１，0）あるいは（0，1）とかける。どっちに進んでも1通りしか存在しない。
ではあと一歩進めてみよう。例えば、（２，0）の点。これは北に2回進むしかないから、これまた1通りしかない。
次に、（１，１）の点。ここは、（１，0）から来る場合と（0，1）から来る場合で合流地点となり、２通りとなる。（２，0）の点と異なり、”合流”することでパターン数がが増える。
このまま続けて本来のBにたどり着いてもいいんだけど、これを一般化して考えてみよう。
ある交点からみたとき、西側からだけやって来る場合と南からだけ来る場合、その両方から来る場合に分類できる。やってくるものは、それまでに形成したパターンを引き連れてくるわけだけど、西か南の一方からのみだったら、引き連れてきたパターン数をそのまま継承するのみとなる。
一方、両方からやって来る場合、それぞれが引き連れてきたパターンの合算がその交点にたどり着く総数となる。
このルールを用いて数字を当てていったのが、下の図だ（矢印がある箇所は、一番左の値）。
ここから、脇においておいた条件、東に連続2回動く場合を除外する必要がある。Aに近いところから順に考えると、（0，1）の点から連続東に進む場合を除外するから、（2，1）の点へのパターンは1通りになる。
（2，2）の点は、除外条件がなければ5パターンある。合流の片方が1になったから、合算値も1小さくなって4になる。ここには、（2，0）を通って東に2回進む場合が含まれるので、その1パターンも引いて3通りとなる。
こういった作業を順次繰り返して行ったものが、上の図だ。まず除外条件なしの場合の数を書いて、すでに修正したところの数字で合流値を洗い替える。最後に、その交点に東に2つ連続で進む方法があれば除算する。
（3，2）の点は、（1，2）の点から東に3回進む場合を除くわけだけど、（1，2）の点にたどり着く3パターンには（2，0）点から東に一つ進むパターンも含まれていて、これはすでに（2，2）の点へのパターン数を計算するときに除外されていることに注意。
この作業により、最終的には10通りとなることがわかる。
場合分けしてもっとスッキリ解く方法あるけど、たまにはこんな亜流な回答も乙かなと。
今回はここまで。
