|
げほげほ |
|
一般に「高さhマス、幅wマス」のケースを解く方法を２つほど書いてみます。
以下、入口の座標を(0,0) カレー店の座標を(w,h)とします 解法１：過去問（第330問）の解法を踏襲 題意を満たすような経路は(0,1),(w-1,h),(w,h-1),(1,0)の４点を この順もしくはこの逆順にちょうど１回ずつ通ることになります。 逆順についてはあとで２倍すればいいので、この順の最短経路を考えましょう。 題意を満たさないものも含めて全て数え上げると ((h+w-2)C(w-1))^2通り ですね。 あとはこれから「行きと帰りで交わってしまうケース」を引けばいいわけですが それは「最初の交点で行きと帰りの経路を取り替える」という操作によって 「(0,1)から(w,h-1)への経路数 × (1,0)から(w-1,h)への経路数」と１：１に対応します。 よって (h+w-2)Cw × (h+w-2)Ch 通りと求めることができます。 つまり答えは ((h+w-2)C(w-1))^2 - ((h+w-2)Cw)*((h+w-2)Ch) を２倍すればよく とくに h=w=3 のケースだと ( (4C2)^2-(4C3)^2 )*2 = (36-16)*2 = 40 となるわけですね！ 解法２：組み合わせ論の知識で殴る（笑） 今回の問題において、題意を満たす経路で囲まれる部分の図形は 「平行四辺形ポリオミノ」と呼ばれるものになります。（図でいうと、赤線と青線に囲まれた部分） 答えは結局のところ「3×3の平行四辺形ポリオミノの個数の２倍」ですね。 一般にh×wの平行四辺形ポリオミノの個数は「ナラヤナ数」というものを用いて N(h+w-1,h) で求められることが知られており N(n,k):=(1/n)(nCk)(nC(k-1)) となっています。 （もちろんこのことは解法１のアイディアを用いて証明することができます。） というわけで求める答えは (1/5)((5C3)*(5C2)) を２倍して 40 となるわけですね！ なお、恥ずかしながら自分は行きと帰りで２倍になることを失念し ドヤ顔で20を送って何故か正解にならないぞとしばらくパニックになっていました…（ |
|
プププランド
9月10日（木） 2:30:55
HomePage:正体不明（あんのうん） 49531 |