ゴールデンウィークなんて、わかってたけど、あっという間だったな。というわけで楽しく問題解いていこう。今回は、ちょっと亜流な解法で。
問題
解説
ありがちな最短経路問題の中で、全体の形が四角じゃない問題。そんなこと無視して、↑に4回、→に3回行けばいいのね、なんてやってはいけない。連続↑に4回とか行けないわけだから、単純に矢印並べではパターンを洗い出せない。
じゃどうするのかというと、原点に戻って考えてみる。必殺技が使えないときには、普通にパンチ・キックで敵に挑むわけだ。場合の数の原点は、丁寧に数えること。このとき、愛言葉は、もれなく、ダブりなく。カッコ良くいえば、MECEとなる。
基本姿勢は、この「もれなく、ダブりなく」(MECE)で、そこから楽をするべく、効率的な数え方を模索していくことになる。
Aを出発して指でなぞりながらBにたどり着く経路を数えるという、長地道な作業をどう効率化できるだろうか。
いくつか解法・考え方はあるけど、まずはシンプルに考えてみる。東に2回連続いかない条件は、否定条件ゆえ、一旦肯定状態である2回連続して東に進む状況を算出し、最後に引くことにしよう。さて、どんな仕組みで各場合は増えていくのだろう。
どれでもいいから、ひとつ経路を取り上げてみる。その経路のどこかの交点で、違う選択肢をとれば、別のパターンが生まれる。つまり、交点がパターンを増やすきっかけになっていると解釈できる。
じゃ、一般に交点でどのようにパターンが増えるのかを考察してみよう。最も単純化したケースからはじめる。最も単純化したケースとは、BをAから一歩目の地点においた場合のものだ。
ここから便宜的に、東方向と北方向にそれぞれ進んだ点を(東、北)と表すことにする。
そうすると、単純化したケースは(1,0)あるいは(0,1)とかける。どっちに進んでも1通りしか存在しない。
ではあと一歩進めてみよう。例えば、(2,0)の点。これは北に2回進むしかないから、これまた1通りしかない。
次に、(1,1)の点。ここは、(1,0)から来る場合と(0,1)から来る場合で合流地点となり、2通りとなる。(2,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通りとなることがわかる。
場合分けしてもっとスッキリ解く方法あるけど、たまにはこんな亜流な回答も乙かなと。
今回はここまで。