体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

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

問題のおさらい

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

以下は、縦 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 列目)の上が白であれば問題ありませんが、黒だと、分断された領域ができてしまいます。

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