経路(AOJ 0547 Commute routes) - こむぎ娘製粉所

休みに入ってから急速にだらけてしまって朝寝夕起きの生活が定着してしまったこむぎ娘です。改善したい。

することがないと家で寝てるだけになってしまうのでどこかに出かけたいけど、お金がなくて遊びに行けない…

さて、今日もAOJの問題なんです。仕方ないね。
解いてみて自分で考えたことを書くだけですが、何かちょっとでもいいことがあるかなと思って。

ヾ(๑╹◡╹)ﾉ"

AOJ 0547 Commute routes

よくありがちな経路問題ですね。格子状の道路で左下から右上までの最短経路が何通りあるかを求める問題です。

この問題では、交差点を曲がった次の交差点では曲がることができないという条件が与えられています。

この条件がない場合、解き方はだいたいの高校で教えられているはずです。多分。
右に移動する回数をa、上に移動する回数をbとすると、経路の総数はn個の要素からk個を取り出す組み合わせC(n, k)を用いてC(a+b, a)で計算することができます。

C(a+b, a)の求め方は複数ありますが、ここでは階乗等を用いず、プログラミングに近い(？)方法
を用いることにします。
組み合わせの性質として、C(n, k) = C(n-1, k) + C(n-1, k-1)というものがあります。これがどういう意味なのでしょうか。

条件がない場合 - プログラムを書いて解くには

先ほどの格子とC(a+b, a) = C(a+b-1, a) + C(a+b-1, a-1)の関係性を考えてみることにします。
始点の位置をP(1, 1)、終点の位置をP(w, h)とします。
終点まで右にa回、上にb回で移動できる位置P(x, y)での経路の総数をC(a+b, a)としました。a+bは移動回数の総数ですね。
C(a+b-1, a)は終点まで右にa回、上にb-1回で移動できる位置での経路の総数であり、これはP(x, y)から上に1つ進んだP(x, y+1)での経路の総数ということになります。
同様にC(a+b-1, a-1)は終点まで右にa-1回、上にb回で移動できる位置、つまりP(x+1, y)における経路の総数です。
つまり、P(x, y)からの経路総数は、そこから右に進んだときの経路総数と上に進んだときの経路総数の和となります。簡単ですね。

これで先ほどの式がどういう意味かが分かったので、具体的な値を求める方法を考えましょう。
終点の位置では、移動しなくても終点に辿り着ける(？)ので、C(0, 0) = 1ということにします。また、任意の自然数nについて、C(n, 0) = C(n, n) = 1、つまり、上のみの移動、もしくは右のみの移動で終点に辿り着ける場合も経路の総数は1通りしかないということです。
今与えた位置以外では、先ほどの式を用いて計算します。

ところで、具体的に値を求めるときに、単純に展開式を与えるだけの関数を作ってしまうと、同じC(a, b)を何度も展開してしまうという事態が発生します。これは無駄なので、一度計算した結果は配列か何かに記録して、次の呼び出しですぐに使えるようにしておくと効率がよくなります。

条件がある場合

問題での条件がない場合ばかり話してしまいましたが、ここからは条件がある場合を考えてみます。

組み合わせを求める関数について、ここでは先ほどのように移動総数と右への移動数を引数に取るのではなく、右への移動数と上への移動数を引数に取る方式にしましょう。つまり、C(a+b, a)の代わりにc(a, b)を考えます。すると、c(a, 0) = 0、c(0, b) = 0、c(a, b) = c(a-1, b) + c(a, b-1)が成り立つことがわかります。

ところが、この問題ではある地点での経路の総数は、その地点に左側から来るか下側から来るかで異なってきます。経路数を求める関数は、来た方向も引数に取る、もしくは関数を2つに分ける必要が出てきます。
ここでは、関数を2つに分けることにします。左から来たときの経路総数をf(a, b)、下から来たときの経路総数をg(a, b)とします。
もし上に移動できる回数が残り1回しかない場合、その点に左から来ると、そこから上に進むことはできません。交差点を曲がった直後はすぐに曲がることはできないという条件があるからです。つまり、そこからひたすら左に進み、突き当りで上に移動して終点に着くという経路1つ以外考えられません。これはf(a, 1) = 1であっることを意味しています。
同様に右に移動できる回数が残り1回しかない場合、その点に下から来ると、経路は1通りしかありません。つまりg(1, b) = 1です。

また、左から来た場合、直進することも上に曲がることもできますが、上に曲がった場合、2回以上上に移動しないと次に曲がることはできないので、f(a, b) = f(a-1, b) + g(a-2, b)となります。
同様にg(a, b) = f(a-2, b) + g(a, b-1)となります。

これを用いて問題を解くことができます。始点が(1, 1)、終点が(w, h)であるので、移動できる回数はa = w-1、b = h-1です。
ここで困ったことが出てきます。始点ではどちらから来たかという情報が存在しません。当然その点から始まるので直前の位置なんてないのです。
しかし、始点から移動できる方向は上か右のどちらかです。つまり、経路の総数は点(2, 1)に左から来たときの経路数f(a-1, b)と点(1, 2)に下から来た時の経路数g(a, b-1)の和となります。

まとめ

f(a, 0) = 1
f(a, 1) = 1
f(0, b) = 1
f(a, b) = f(a-1, b) + g(a, b-2)
g(a, 0) = 1
g(0, b) = 1
g(1, b) = 1
g(a, b) = f(a-2, b) + g(a, b-1)

以上の関数を定義してあげれば、wとhが与えられたときにf(w-2, h-1) + g(w-1, h-2)を計算し表示すればいいということになります。当然高速化のためにメモ化とかは必要になると思いますが。

なお、この問題では100000による剰余を表示することになっていますが、2つの和となっているところで剰余を取ってあげれば大丈夫です。また、100000未満の2項の和は200000以上になることはないので、剰余演算子を使わずに100000以上になったときに100000を引けば高速にできるのではないでしょうか。

(｡>﹏<)ノ

かなり長くなってしまいました。
自分の言葉でまとめてみたけど分かりづらいですね。日本語難しい:;(∩´﹏`∩);:

私はこういう問題好きです。経路とかそういうのとか。
関数の再帰みたいな感じで求めることができるのが楽しいというかなんというか。ふがふが。

そんなことより日本語って難しいですね。使いこなせる気がしません。