ガジェット通信 GetNews

見たことのないものを見に行こう
「ジャスティス・リーグ」特集サイト

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

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

問題のおさらい

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

以下は、縦 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+1 = An+Bn+Cn+Dn+En という漸化式が成り立ちます。

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

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+1 = An+C(a)n+Dn です。

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

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

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

あとは、初期値として列ベクトル (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さんの次の問題にご期待ください。

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