ガジェット通信

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「レッド・アンド・ホワイト」問題解説

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

問題のおさらい

マス目が横に直線状に並んでいます。
マス目は左右にどこまでも続いているものとします。
マス目はすべて白色で塗られています。

このうちの 1 つを赤色で塗ります。
以降、次のルールに従って、マス目の色を塗り替えていきます。

1 秒後、左右隣のマス目の色が白赤または赤白となるマス目を全て赤色で塗り、そうでないマス目(つまり左右隣が白白または赤赤)を全て白色で塗ります。
以降、同様に、1 秒ごとに赤白でマス目を塗り替えていきます。

以下は、初期状態(0 秒後)から始めて、1 秒後、2 秒後、3 秒後の様子を示しています。

自然数 n に対し、n 秒後の赤色のマス目の個数を F(n) と定義します。

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

同様に、F(10) = 4,F(31) = 32,F(1023) = 1024,F(12345) = 64 となることが確かめられます。

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

方針

本問は、問題文だけを見て考えてみても、解法がすっと浮かぶことは難しいと思います。そこで解決のためのアプローチとして、実際に手を動かしてみる ことをやってみましょう。

ノートに線を引いて、赤白の変化がどうなるか、追いかけてみましょう。描きすぎかな? と思うぐらいまでやってみましょう。実験用のコードを書いてみてもいいかもしれません。

12秒後までの変化を記しました。ここまで描くと、パターンが見えてくると思います。

それは次のような規則です。整数 k に対し、0 秒後から 2k-1 秒後までの行を取り出したものを Tk と呼ぶことにします。すると以下の通り、Tk は Tk-1 を 3 つ組み合わせ、さらに隙間を白マスで埋めることによって構成されているのです。

本記事では証明を省略しますが(Tk の最下辺に常に赤白が交互に並ぶことを利用して帰納法で証明できます)、どのような k についてもこの関係が成り立っています。

赤マスの数を再帰的に数える

それでは n 秒後の赤マスの個数はどのように数えればよいでしょうか。そのために、「図形 Tk の第 m 行目(ただし最上を第 0 行目とする)に赤マスは何個あるか?」を考えましょう。

これを Sk(m) とおきます。すると、Sk(m) は、第 m 行目が Tk の上半分(第 0 行目~第 2k-1-1 行目)にあるときと、下半分(第 2k-1 行目~第 2k-1 行目)にあるときとで場合分けすればよいと分かります。上半分の場合は、Sk(m) は Sk-1(m) に等しく、下半分の場合は、Sk(m) は Sk-1(m-2k-1) の 2 つぶんに等しくなります。

上記の漸化式をコードにしましょう。適当な大きさの k(n < 2k となる k)を初期値とし、漸化式を繰り返し適用します。再帰を使うと楽に書けます。

コード例は以下です(C++)。

#include
using namespace std;

int S(int k, int m) {
if (k == 0) return 1;
if (m < (1 n;
// n < 2^k となる最小の k を求める.
while (p

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

TOP