読者です 読者をやめる 読者になる 読者になる

Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

パスカルの 三角形では ありません(字余り) の解説解題

CodeIQ に、「パスカルの 三角形では ありません(字余り)」( https://codeiq.jp/q/2630 ) という問題を出していたんだが、先日締め切られた。

で。解説解題。

二次元の表に数字が埋まっていて、表外の数字を外挿して計算せよ、という問題。

表の数字などについては
http://ange1.hateblo.jp/entry/2016/09/06/124121
を参考にしていただくとして、規則性の方はタイトルの通りパスカルの三角形からヒントを得た二次元数列になっていて。
左上隅を {a(0,0)} とすると、こんな感じ:

{ \displaystyle
a(x,y)=1~~if~x<0~\lor~y<0
}
{ \displaystyle
a(0,0)=1
}
{ \displaystyle
a(x,y)=a(x-1,y)+a(x,y-1)+a(x,y-2)~~otherwise
}

で。これを定義のとおりに計算すれば良いという簡単な問題だったつもり。まあ計算量を減らすためにメモ化ぐらいはした方がいい。

とはいえ。

ルールが簡単なので、漸化式ではない形にできてしまう。

計算のために、先ほどの式に以下のように意味づけする:

縦の道が x+1 本。横の道が y+1 本ある経路を左上から右下まで最短経路で行く方法の場合の数。ただし、横方向に行く方法は、1マス進む「歩く」と、2マス進む「ジャンプ」の2通りがある。そして「歩く」と「ジャンプ」は区別する。

で。

ジャンプが n回の場合を考える。
ジャンプをいつ使うのかを気にしなければ、横方向のマスが n 個減った場合と同じなので
{\binom{x+y-n}{y-n}}
となる。
横方向の移動は x-n 回ある。そのうち n 回「ジャンプ」を使うのでジャンプする場所の選び方は
{\binom{x-n}{n}}
となる。
したがって、ジャンプが n 回の場合の場合の数は
{\binom{x+y-n}{y-n}×\binom{x-n}{n}}
になる。
ジャンプの回数は 0回以上 {\lfloor x/2 \rfloor}回以下なので、

{\displaystyle a(x,y)=\sum_{n=0}^{\lfloor x/2 \rfloor}{\binom{x+y-n}{y-n}×\binom{x-n}{n}}}

となる。

とまあ、こんな計算をしてもいいんだけど、むしろこちらは想定外。

想定解答はあくまでもメモ化付きの漸化式なのでありました。