CodeIQ MAGAZINECodeIQ MAGAZINE

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

2017.05.22 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 10
  • このエントリーをはてなブックマークに追加
riverplus

「数学の問題をプログラミングで解こう!」シリーズ。チェス盤でのルークの置き方に関する問題でした。いろいろな解き方が可能な問題です。

みなさんはうまくできましたか?ぜひ出題者のKawazoeさんによる本記事で解法をチェックして下さい!
by CodeIQ運営事務局

問題のおさらい

自然数 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 ≦ km の範囲の自然数 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 です。

標準入力から、自然数 nm (1 ≦ n ≦ 4, 1 ≦ mn2)が半角空白区切りで与えられます。
標準出力に 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) にルークがあるかどうかは、整数の第 xny ビットが 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<<(n*y+x))) > 0

def num_of_rook(s):
    r = 0
    for x in range(n):
        for y in range(n):
            if has_rook(s, x, y): r += 1
    return r

def is_hagure(s, x, y):
    if not has_rook(s, x, y): return False
    for p in range(n):
        if p != y and has_rook(s, x, p): return False
        if p != x and has_rook(s, p, y): return False
    return True

def num_of_hagure(s):
    r = 0
    for x in range(n):
        for y in range(n):
            if is_hagure(s, x, y): r += 1
    return r

def binomial(a, b):
    c = 1
    for i in range(b):
        c *= a-i
        c /= i+1
    return c

n, m = map(int, raw_input().split())

count = [0 for i in range(n*n+1)]
for s in range(2**(n*n)):
    h = num_of_hagure(s)
    r = num_of_rook(s)
    count[r] += h

answer = 0.0
for k in range(1, m+1):
    answer += float(count[k]) / binomial(n*n, k)
print int(1000 * answer)

方針2:和の期待値は期待値の和

もう一つのやり方を紹介します。期待値に関する公式を活用します。次の公式です。

参考:期待値 – 性質(Wikipedia)

F(n, k) の定義は「はぐれルークの個数」の期待値でした。この「はぐれルークの個数」を上の XY と見て、次のように分解してみましょう。「はぐれルークの個数」=「マス(0, 0)のはぐれルークの個数」+「マス(0, 1)のはぐれルークの個数」+「マス(0, 2)のはぐれルークの個数」+…+「マス(n-1, n-1)のはぐれルークの個数」。要するにマス全体をマス個別に分解したということです。

ここから期待値を出しましょう。上の公式を使って、次のように書けるのがミソです。「はぐれルークの個数の期待値」=「マス(0, 0)のはぐれルークの個数の期待値」+「マス(0, 1)のはぐれルークの個数の期待値」+「マス(0, 2)のはぐれルークの個数の期待値」+…+「マス(n-1, n-1)のはぐれルークの個数の期待値」。

この「マス(x, y)のはぐれルークの個数の期待値」は、要するに「マス(x, y)にはぐれルークがある確率」のことです。マス(x, y) がはぐれルークである置き方とは、下図で言うと、マス(x, y)にルークがあり、かつ水色のマスにルークが 1 個もなく、さらに黄色のマスに残り k-1 個のルークがある置き方です。そのような置き方は何通りあるかというと、黄色のマス((n-1)2 個)から k-1 個を選ぶ場合の数ですから、(n-1)2Ck-1 通りです。したがって確率は (n-1)2Ck-1÷n2Ck です。

他のマス (x, y) についても確率は同じです。したがって、「はぐれルークの個数の期待値」は、上の確率を n2 倍したものになります。以上から、F(n, k) は次のように書けます。

1 ≦ km の範囲の自然数 k について、上の式で F(n, k) を一つずつ求めるコードを書けば G(n, m) が求められます。方針1よりずっと短い実行時間でクリアできます。

さらなる高速化を紹介します。実は F(n, k) には次の漸化式が成り立ちます。(実際に上の公式を代入して確認してみて下さい。)

G(n, m) を計算するときにこの漸化式を使うと、ひとつ前の F(n, k) の値から簡単な計算で次の F(n, k+1) の値が求められます。

コードは次のようになります。かなりスッキリしましたね。実行時間も短く、もっと大きな n, m の値に対しても答えが出せます。

n, m = map(int, raw_input().split())

answer, f = 0.0, 1.0
for k in range(1, m+1):
    answer += f
    f *= float((n-1)*(n-1)-k+1) / (n*n-k) * (k+1) / k
print int(1000 * answer)

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックして下さい。

CodeIQ「ロンリー・ルーク」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
Kawazoeさんの次の問題にご期待ください。

  • 10
  • このエントリーをはてなブックマークに追加

■関連記事

数学の問題をプログラミングで解こう!「タンジェント・フラクション」問題解説... 問題のおさらい α と β を、0 < α < β < π/2 を満たす実数とします。 α, β の組のうち、tan(α), tan(β), tan(α+β) がすべて単位分数(分母が自然数、分子が 1 の分数として書き表せる数)となるものを考えましょう。(α, β の単位はラジアンと見なします...
【謎解きプログラム】どう比較する?【ソート】解答と解説... 【謎解きプログラム】どう比較する?【ソート】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以内に謎...
【謎解きプログラム】どんな数字になる?【整数のキャスト】解答と解説... 【謎解きプログラム】どんな数字になる?【整数のキャスト】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24...
【謎解きプログラム】テキストのバイナリは?【テキスト バイナリ】解答と解説... 【謎解きプログラム】テキストのバイナリは?【テキスト バイナリ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 ...
【謎解きプログラム】条件に当てはまる文字列は?【正規表現】解答と解説... 【謎解きプログラム】条件に当てはまる文字列は?【正規表現】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「2...
数学の問題をプログラミングで解こう!「クロッシング・ワード」問題解説... 問題のおさらい クロスワードの盤面では、格子状のマス目に白マスまたは黒マスを配置します。 以下は、縦 3 個×横 4 個のマス目に白マス・黒マスを配置する例です。 白マス・黒マスの配置には次のルールがあります。 黒マスによって白マスの領域が分断されてはならない。 黒マスが縦・横に連続し...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ