CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「クロッシング・ワード」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
クロスワードの有効な盤面の数を求める問題でした。
今回はかなり難しかったと思います。

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

問題のおさらい

クロスワードの盤面では、格子状のマス目に白マスまたは黒マスを配置します。

以下は、縦 3 個×横 4 個のマス目に白マス・黒マスを配置する例です。

白マス・黒マスの配置には次のルールがあります。

  • 黒マスによって白マスの領域が分断されてはならない。
  • 黒マスが縦・横に連続してはならない。

例えば以下は不適切な配置例です。

自然数 n に対して、縦 3 個 × 横 n 個のマス目に白マス・黒マスを配置する場合の数を F(n) と定義します。

例えば F(1)=4,F(2)=11 です。以下に n=2 の場合の配置の仕方を示します。

同様に、F(3)=39,F(4)=121,F(5)=387 となることが確かめられます。

標準入力から、自然数 n(1 ≦ n ≦ 108)が与えられます。
標準出力に F(n) を 106 で割った余りを出力するプログラムを書いてください。

方針:一つ手前の状態で場合分け。しかし落とし穴が…

クロスワードで有効な盤面の数を求める問題です。過去に CodeIQ で同じ設定の問題がありました。あちらは盤面の最大サイズが 5×6 でしたが、今回は 3×108 と、横が極端に長くなっています。この特徴をうまく使うことがポイントとなります。

まず素直に思いつく解法は、条件を満たす盤面を全列挙する方法です。盤面が小さければこの方法はうまくいくでしょう。ですが、今回のように大きなサイズでは到底うまくいかないことは、容易に想像つくと思います。

そこで本問では、この記事でもたびたび登場した「一つ手前の状態に着目する」という考え方を使いましょう(数学の問題をプログラミングで解こう!「キャリー・オーバー」問題解説)。自然数 n に対し、サイズが 3×n のときと 3×(n+1) のときとの間にどのような関係があるかを考えていきます。

まずは定式化です。3×n での白マス・黒マスの配置の仕方を、「右端列の並び方によって次の 5 通りに分類してみます。

それぞれの場合の数を An, Bn, Cn, Dn, En とします。

An, …, En の値が全て分かっていたと仮定します。このとき、n+1 の場合の数、つまり An+1, Bn+1, Cn+1, Dn+1, En+1 はどのように求められるでしょうか?

An+1 を例にしましょう。右端の列がパターン 1 であるような配置です。その一つ左隣の列は、パターン 1~5 のいずれかがあり得ますから、An+1AnBnCnDnEn という漸化式が成り立ちます。

Bn, Cn, Dn, En についても同様にすれば漸化式が導けるわけですが、ここに大きな落とし穴があります。例えば Bn+1、つまり右端がパターン 2 の場合です。この左隣の列には、一見、パターン 3 が来れそうです。しかし、さらにその左隣の列(左から n-1 列目)の上が白であれば問題ありませんが、黒だと、分断された領域ができてしまいます。

つまり、この問題は、左隣の列(n 列目)だけを見ていたのではダメで、さらにその左隣の列(n-1 列目)も合わせて考慮しないといけないのです。

パターン 3 を細分化しましょう。次の 4 通りです。n-1 列目の上(または下)が黒か白かによって 3 通りに分け、それぞれの場合の数を C(a)n, C(b)n, C(c)n とおいています。さらに、n-1 列目が外壁の場合もあります(要は n=1)。この場合の数を C(d)n とおいています。

以上の 8 個のパターンの間の漸化式を導出していきます。例えば Bn+1 については、左隣の列がパターン 1, 3a, 4 であれば、n+1 列目にパターン 2 が来ることができます。したがって、Bn+1AnC(a)nDn です。

他の変数についても同様に導出します。詳しい過程は省略します。結果は以下のようになります。行列の形で表しています。

あとは、初期値として列ベクトル (A1, B1, C(a)1, C(b)1, C(c)1, C(d)1, D1, E1) = (1, 1, 0, 0, 0, 1, 1, 1) に対して、上記の行列を (n-1) 回、繰り返しかけ算していきます。結果得られた列ベクトルは、3×n のマス目の埋め方を右端列の並びで分類したものになります。パターン 3b, 3c, 3d は不適切ですから、それら以外の成分の和が、求めるべき答えとなります。

実装

以上を実装しましょう。今回は n の上限が 108 と大きいため、行列の掛け算を n 回行うのは処理時間的によくありません。行列のべき乗を用いて高速に計算しましょう。(数学の問題をプログラミングで解こう!「ルート・パワー」問題解説

コード例は以下です。n=1 の場合だけ、パターン 5 が不適ですので、例外的に答えから 1 引いている点に注意して下さい。

D = 1000000

def mul(x, y):
    z = [[0 for i in range(len(y[0]))] for j in range(len(x))]
    for i in range(len(x)):
        for j in range(len(y[0])):
            for k in range(len(x[0])):
                z[i][j] = (z[i][j] + x[i][k] * y[k][j]) % D
    return z

def pow(x, m):
    if m == 1: return x
    if m % 2 == 0:
        p = pow(x, m / 2)
        return mul(p, p)
    else:
        p = pow(x, m - 1)
        return mul(x, p)

matrix = [
    [1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 0, 0, 0, 1, 0],
    [1, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0],
]

vector = [[1], [1], [0], [0], [0], [1], [1], [1]]

n = int(input())
p = pow(matrix, n-1)
q = mul(p, vector)
answer = q[0][0] + q[1][0] + q[2][0] + q[6][0] + q[7][0]
if n == 1: answer -= 1

print answer % D

高速化の手法については、上記の行列のべき乗のほか、106 での余りの周期性を利用する方法もあります(数学の問題をプログラミングで解こう!「トライアングル・メイズ」問題解説)。詳細については割愛します。

みんなのコード

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

CodeIQ「クロッシング・ワード」問題 みんなのコード

CodeIQ運営事務局より

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

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

■関連記事

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説... 問題のおさらい 自然数 a, b に対し、a と b の最小公倍数を LCM(a, b) と定義します。 例えば、LCM(6, 8)=24 です。 さらに、自然数 n, k に対し、n 以下の全ての自然数 m に対する LCM(k, m)÷k の値の和を F(n, k)と定義します。 例えば ...
数学の問題をプログラミングで解こう!「タワー・ビルディング」問題解説... 問題のおさらい A を一辺が 1 の立方体のブロックとし、B を縦が 1、横が 1、高さが 2 の直方体のブロックとします。 (下は横から見た図です。) 自然数 n, a, b に対し、A を最大 a 個、B を最大 b 個使って、縦が 1、横が 1、高さが n の直方体の塔を作ります。 こ...
数学の問題をプログラミングで解こう!「ペア・ドロップ」問題解説... 問題のおさらい n を自然数とします。1 から n までの自然数が 1 つずつ書かれた n 枚のカードが 2 組あります。 これら 2n 枚のカードをよく混ぜ、A と B の 2 人に n 枚ずつ配ります。 A と B は、それぞれ自分の持ち札の中に番号が一致するカードがあればその 2 枚を捨...
数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説... 問題のおさらい 2 以上の自然数 n に対し、n×n の格子状に並んだ点を考えます。 これらの点のうちちょうど 2 個の点を通る直線の数を F(n) と定義します。 例えば F(2)=6 です。題意を満たす直線は以下の 6 通りです。 また、F(3)=12 です。題意を満たす直線は以下の...
数学の問題をプログラミングで解こう!「ループ・トラッキング」問題解説... 問題のおさらい 自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。 例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。 さて、整数 k(0 ≦ k ≦ n)に対して、関数 Fn による変換を繰り返し行い...
数学の問題をプログラミングで解こう!「カウント・スリー」問題解説... 問題のおさらい 自然数を 1 から順に書き並べていきます。 このとき、3 の数字が現れる回数を数えます。 自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。 例えば F(10)=35 です。 下の通り、10 個目の 3 は、35 を書いて...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

リクルートへ