ガジェット通信 GetNews

見たことのないものを見に行こう
ワンダーウーマン

数学の問題をプログラミングで解こう!「ロンリー・ルーク」問題解説

DATE:
  • ガジェット通信 GetNewsを≫

問題のおさらい

自然数 n, k に対し、縦横 n×n のマス目にチェスのルークの駒を k 個配置することを考えます。

このとき、自身から見て上下方向・左右方向のいずれにも他の駒が存在しないような駒を「はぐれルーク」と呼びます。

例えば以下は、(n, k)=(4, 5) のときの駒の配置例を示しています。
それぞれ、はぐれルークを灰色丸、そうでないルークを青色丸で示しています。
また、はぐれルークの個数は、左図では 1 個、右図では 2 個であることが分かります。

数学の問題をプログラミングで解こう!「ロンリー・ルーク」問題解説

さて、1 つのマスに 2 個以上の駒を置かないよう、ランダムに駒を配置します。
このとき、はぐれルークの個数の期待値を F(n, k) と定義します。

例えば F(2, 2)=2/3 です。

可能な駒の配置は以下の 6 通りです。このうち真ん中の 2 通りでのはぐれルークの個数は 2 個で、他の 4 通りでは 0 個です。
したがって期待値は、0×(4/6)+2×(2/6) = 2/3 となります。

数学の問題をプログラミングで解こう!「ロンリー・ルーク」問題解説

同様に、F(2, 1)=1, F(4, 2)=1.2, F(3, 3)=0.642…, F(4, 5)=0.461…, F(4, 11)=0 となることが確かめられます。

さらに、自然数 n, m に対し、1 ≦ k ≦ m の範囲の自然数 k に対する F(n, k) の和を G(n, m) と定義します。

例えば、G(2, 2)=5/3, G(4, 3)=3.228…, G(4, 5)=4.428… となることが確かめられます。

また、103×G(n, m) の整数部分を H(n, m) と定義します。

例えば、H(2, 2)=1666, H(4, 3)=3228, H(4, 5)=4428 です。

標準入力から、自然数 n と m (1 ≦ n ≦ 4, 1 ≦ m ≦ n2)が半角空白区切りで与えられます。
標準出力に H(n, m) の値を出力するプログラムを書いてください。
なお全てのテストケースにおいて、103×G(n, m) の値と、最も近い整数値との差の絶対値は 10-3 以上であることが保証されています。

方針1:総当たりでなんとかなる

本問は、さまざまなやり方で解けるよう、少し緩めの上限としました。始めに、総当たりによる方法を紹介した後で、上級編の解き方として、期待値の線形性をつかった方法を紹介します。

まずは、総当たりの方法です。本問では盤の大きさが最大でも 4×4 ですから、ルークの置き方はたかだか 216=65536 通りです。この程度なら、置き方すべてを列挙するようなコードでも 1 秒の制限時間に間に合うのではと予測が立ちます。

全ての置き方を列挙するには、どのようなコードを書けばよいでしょうか。再帰などいろいろな書き方がありますが、ここではビットを使った書き方を示します。

各マスのルークの ある/なし を二進数のビット 1/0 とみなし、1 つの盤面を 1 つの整数に対応づけるという考え方です。盤の左上のマスを、ビット列の最下位ビットに対応づけます。さらにその右隣りのマスを 2 番目のビットに対応付けます。以降、同様にして、n2 個のマスをそれぞれ二進数の 1~n2 番目のビットに対応づけます。こうすることで、すべての盤面を 0 以上 2n2 未満の整数との間で 1 対 1 で対応づけることができます。

盤面と整数の対応の例を下図に示します。

数学の問題をプログラミングで解こう!「ロンリー・ルーク」問題解説

0 から 2n2-1 までの整数についてループを回しましょう。1 つの整数を 1 つの盤面とみなします。各盤面について、マスをひとつひとつ見て、ルークがあるかどうかを調べます。左上マスを (0, 0)、右下マスを (n-1, n-1)とするとき、(x, y) にルークがあるかどうかは、整数の第 x+n・y ビットが 1 かどうかです。もしルークがあれば、その上下左右に他のルークがないかを調べて、はぐれルークの判定を行いましょう。

はぐれルークの個数が分かったら、ルークの個数を引数とする整数の配列(下記コードでは count)に、その数を足します。配列でデータを持っておくことで、G(n, m) を求めるときに、さまざまな m に対してその都度 F(n, k) を計算するのでなく、まとめて計算することができます。結果、配列 count[k] には、ルークが k 個である全ての置き方に対するはぐれルークの総数が収められます。これを、n2 個のマスに k 個のルークを置く場合の数、つまり nCk で割れば、F(n, k) の値が求められます。

説明が長くなりました。コード例(Python)は以下です。

def has_rook(s, x, y):
return (s & (1

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。