「ロンリー・ルーク」問題解答 ( CodeIQ )
CodeIQというところでプログラミング問題「ロンリー・ルーク」に解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 空白区切りで入力される $n,m\,( 1\le n\le 4,\,1\le m\le n^2 )$に対して、$H(n,m)$の値を出力する
- $H(n,m)$は次のように定義される
- $H(n,m)=\lfloor 1000G(n,m)\rfloor$
- $G(n,m)=\sum_{k=1}^{m} F(n,k)$
- $F(n,k)$は次のように定義される
- $n\times n$のマス目に$k$個のルーク( チェスの駒 ) を配置した時の、「はぐれルーク」の個数の期待値 ( 全配置方法とも等確率とする ) を$F(n,k)$とする
- 「はぐれルーク」とは、そのルークが次に移動可能なマス ( 同じ行・列のマス ) のいずれにも、別のルークが存在しないものを指す
例えば、下の図での灰色の駒が「はぐれルーク」となります。チェスのルークというのは、将棋での飛車に当たりますので、そちらで考えた方がイメージしやすいかも知れません。
解説
提出版
実を言うと、$F(n,k)$は次の式で表すことができます。 $$ F(n,k)=\left\{\begin{eqnarray} &\,&\frac{ {}_{(n-1)^2}P_{k-1} }{ {}_{n^2-1}P_{k-1} }\cdot k\,\,\,\,&\,&( 1\le k \le(n-1)^2+1 )\\ &\,&0&\,&( other ) \end{eqnarray}\right. $$
そして、P の絡む部分は漸化式$\frac{ {}_{(n-1)^2}P_{k} }{ {}_{n^2-1}P_{k} }=\frac{ {}_{(n-1)^2}P_{k-1} }{ {}_{n^2-1}P_{k-1} }\cdot \frac{(n-1)^2-(k-1)}{n^2-k}$で計算できますから、この漸化式を回しながら有理数的に総和を計算することで答えを求めることができます。
ということで、次のRuby(98)を提出しました。
なんと。複雑な問題と思いきや、100文字を切る実装が可能です。t の計算をt=2-n*2+n*=nとした方が3文字短かったわけですが、まあそこはうっかりさんでした。
なお、$k\gt(n-1)^2+2$では総和を計算する意味はないのですが、計算に使っている分子部分 ( 変数d ) はそこからずっと 0 なので、ループを打ち切らなくとも結果には影響ありません。
詳細
まずどこから取り掛かるか、ですが、はぐれルークの個数それぞれに応じた配置が何通りあるのかから考えてみます。
全体のマス $n\times n$、ルークの数 $k$、はぐれルークの数 $i$ の場合、はぐれルークは$i$行$i$列分の領域に行・列かぶらないように配置されるので、$({}_nC_i)^2\cdot i!$通りです。
が、$(n-i)\times(n-i)$のマスに押し込められる、はぐれでないルーク、この配置が何通りあるかが良く分かりません。そこで$x\times x$のマスに$y$個のルークをはぐれなしで配置する場合の数を$P(x,y)$と置き、この値にフォーカスしていきます。
先に進む前に、このPを使ってFを表しておきます。次のようになります。
- $F(n,k)=\frac{1}{{}_{n^2}C_k}\sum_{i=1}^n i({}_nC_i)^2i!\cdot P(n-i,k-i)$
さて。では「はぐれルークなし」の場合の数 P ですが、これは全体のパターン数から各はぐれルークの数に応じたパターンを差っ引く形で漸化式を立てることができます。すなわち、
- $P(x,y)=C(x,y)-\sum_{i=1}^x ({}_xC_i)^2 i!\cdot P(x-i,y-i)$
- $C(x,y)={}_{x^2}C_{y}\,\,( 0\le y\le x^2 )\,\,or\,0\,( other )$
こうして漸化式が立ったわけですが、$\sum$を都度計算する必要があるようだと面倒くさい形です。しかし、良く見てみると値の由来は ( 係数を除いては ) 必ず C になっていることに気付きます。ということは、PはCに適当な係数をかけた積和の形で表せるのではないかと考えます。その係数をAとしてみます。
- $P(x,y)=\sum_{i=0}^x A(x,i)C(x-i,y-i)$
あくまで漸化式に効いてくるのは ( 総和の項数に影響する ) $x$ なので、A のパラメータは$x,i$の2種類で済むはずです。このようにしておいて先ほどのPの形と比較し、Aを探っていきます。
$$ \begin{eqnarray} &\,&C(x,y)-\sum_{i=1}^x ({}_xC_i)^2 i!\cdot \sum_{j=0}^{x-i} A(x-i,j)C(x-i-j,y-i-j)=\sum_{i=0}^x A(x,i)C(x-i,y-i) \\ &\Leftrightarrow& C(x,y)-\sum_{h=1}^x \sum_{i=1}^h ({}_xC_i)^2 i!\cdot A(x-i,h-i)C(x-h,y-h)=\sum_{i=0}^x A(x,i)C(x-i,y-i) \\ &\Leftrightarrow& C(x,y)(A(x,0)-1)+\sum_{i=1}^x C(x-i,y-i)\left( A(x,i)+\sum_{j=1}^i ({}_xC_j)^2 j!\cdot A(x-j,i-j) \right)=0 \\ \end{eqnarray} $$
途中で添え字の付け替えを行っているので少しややこしいです。1行目から2行目は、$i+j$の値を$h$として、2重和を三角形的に整理し直しています。その後2行目から3行目では、同じCの項毎に係数をまとめています ( ここで $(h,i)\rightarrow(i,j)$の付け替えを行っています )。
ともあれ、これでAの姿が見えました。 $$ A(x,y)=\left\{\begin{eqnarray} &\,&1&(& y=0 ) \\ &\,&-\sum_{i=1}^x ({}_xC_i)^2 i!\cdot A(x-i,y-i)\,\,&(& 1\le y\le x) \\ \end{eqnarray}\right. $$
なお、$0\le y \le x\le 4$の範囲でのAの実際の値は、次の表のようになっています。
$$ \begin{array}{|cc|cccc|} \hline & & & & x \\ & & 0 & 1 & 2 & 3 & 4 \\ \hline & 0 & 1 & 1 & 1 & 1 & 1 \\ & 1 & - & -1 & -4 & -9 & -16 \\ y& 2 & - & - & 2 & 18 & 72 \\ & 3 & - & - & - & -6 & -96 \\ & 4 & - & - & - & - & 24 \\ \hline \end{array} $$
というところで、ようやくFに戻ってきます。
$$ \begin{eqnarray} F(n,k)&=&\frac{1}{C(n,k)}\sum_{i=1}^n i({}_nC_i)^2i!\cdot P(n-i,k-i) \\ &=&\frac{1}{C(n,k)}\sum_{i=1}^n i({}_nC_i)^2i!\cdot \sum_{j=0}^{n-i} A(n-i,j)C(n-i-j,k-i-j) \\ &=&\frac{1}{C(n,k)}\sum_{i=1}^n C(n-i,k-i) \sum_{j=1}^i j({}_nC_j)^2 j!\cdot A(n-j,i-j) \end{eqnarray} $$
そうすると残りは、2重和の内側の計算です。これを$B(n,i)$とします。すなわち、
- $B(n,i)=\sum_{j=1}^i j({}_nC_j)^2 j!\cdot A(n-j,i-j)\,\,\,( 1\le i\le n )$
これを実際に計算してみると、$B(n,1)=n^2$であることは容易に分かります。では他の項は…? というと、実は全部 0 なのです。
ということで、次のようにして冒頭の式が導かれます。
※ ただし $k \lt(n-1)^2+2$ の場合です。k が大きい場合はそもそも$C(n-1,k-1)=0$ですから$F(n,k)=0$となります。
$$ \begin{eqnarray} F(n,k)&=&\frac{1}{C(n,k)}\sum_{i=1}^n C(n-i,k-i)B(n,i) \\ &=&\frac{C(n-1,k-1)B(n,1)}{C(n,k)} \\ &=&\frac{n^2C(n-1,k-1)}{C(n,k)} \\ &=&\frac{n^2{}_{(n-1)^2}C_{k-1}}{{}_{n^2}C_k} \\ &=&\frac{n^2\cdot (n-1)^2!(n^2-k)!k!}{n^2!((n-1)^2-(k-1))!(k-1)!} \\ &=&\frac{(n-1)^2!}{((n-1)^2-(k-1))!}\cdot\frac{(n^2-k)!}{(n^2-1)!}\cdot k \\ &=&\frac{{}_{(n-1)^2}P_{k-1}}{{}_{n^2-1}P_{k-1}}\cdot k \end{eqnarray} $$
…冒頭の式が導かれたのは良いのですが、なんともご都合主義過ぎやしないかとも思えます。なので、本当に各Bの値が 0 なのかも確かめてみます。$2\le i\le n$に対して、
$$ \begin{eqnarray} B(n,i)&=&\sum_{j=1}^i j({}_nC_j)^2 j!\cdot A(n-j,i-j) \\ &=&n^2A(n-1,i-1)+\sum_{j=2}^i j({}_nC_j)^2 j!\cdot A(n-j,i-j) \\ &=&n^2A(n-1,i-1)+\sum_{j=1}^{i-1} (j+1)({}_nC_{j+1})^2 (j+1)!\cdot A(n-j-1,i-j-1) \\ &=&n^2A(n-1,i-1)+\sum_{j=1}^{i-1} (j+1)\left(\frac{n!}{(n-j-1)!(j+1)!}\right)^2 (j+1)\cdot j!\cdot A(n-1-j,i-1-j) \\ &=&n^2A(n-1,i-1)+\sum_{j=1}^{i-1} \left(\frac{(j+1)\cdot n\cdot (n-1)!}{(n-j-1)!(j+1)\cdot j!}\right)^2 j!\cdot A(n-1-j,i-1-j) \\ &=&n^2A(n-1,i-1)+\sum_{j=1}^{i-1} n^2\left(\frac{(n-1)!}{(n-j-1)!j!}\right)^2 j!\cdot A(n-1-j,i-1-j) \\ &=&n^2\left( A(n-1,i-1)+\sum_{j=1}^{i-1} ({}_{n-1}C_j)^2 j!\cdot A(n-1-j,i-1-j) \right) \\ \end{eqnarray} $$
これを、前に導出した $A(x,y)=-\sum_{i=1}^x ({}_xC_i)^2 i!\cdot A(x-i,y-i)\,\,( 1\le y\le x)$ と見比べてみると、括弧の中がまるっと消えて、ちゃんと 0 になることが分かります。めでたしめでたし。
終わりに
なかなか形をまとめることができず、GWの前半かなり悩みましたが、できてみるとかなり簡単な形にまとめることができてスッキリした問題でした。
※なんか式を弄んでるだけの記事になったきらいがないでもないですが、まあ気にしない
