CodeIQ MAGAZINECodeIQ MAGAZINE

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

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
あるルールに従って赤白が変わるマスに関する問題です。一般には「1次元セルオートマトン」という名前で知られています。一見複雑ですが、うまく考えると非常にシンプルに解けます。

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

問題のおさらい

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

このうちの 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 と呼ぶことにします。すると以下の通り、TkTk-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 つぶんに等しくなります。

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

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

#include <iostream>
using namespace std;

int S(int k, int m) {
    if (k == 0) return 1;
    if (m < (1 << (k - 1))) return S(k - 1, m);
    else return 2 * S(k - 1, m - (1 << (k - 1)));
}

int main() {
    int n, k = 0, p = 1;
    cin >> n;
    // n < 2^k となる最小の k を求める.
    while (p <= n) {
        p *= 2;
        k++;
    }
    cout << S(k, n) << endl;
}

これって要するに・・・

以上、解き方を紹介しましたが、実はこの問題、n の二進数での表現と深いかかわりがあることに気づかれたでしょうか。実は上のコードは、二進数での各桁を見て 1 があれば変数 p を倍にする、という処理と本質的には同じです。

つまり、二進数での 1 の数 を q としたとき、本問の答えは 2q であるということです。実際、本問では多くの挑戦者の方がこの関係を見抜いておられました。この事実を使うと、さらにコードをすっきり書けますね。

参考:パスカルの三角形と 2 進法(外部サイト:pdf)

みんなのコード

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

CodeIQ「レッド・アンド・ホワイト」 みんなのコード

CodeIQ運営事務局より

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

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

■関連記事

【謎解きプログラム】乱数で発生する数値は?【組み合わせ】解答と解説... 【謎解きプログラム】乱数で発生する数値は?【組み合わせ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24...
「放物線とマス目の関係」問題の解答と解説... table.nabe{ margin-left:30px; } .nabefloat{ float:right; } table.nabe td, table.nabe th{ padding:3px; } table.nabe th{ ...
【謎解きプログラム】データをバイナリで見てみよう【バイナリ】解答と解説... 【謎解きプログラム】データをバイナリで見てみよう【バイナリ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「...
数学の問題をプログラミングで解こう!「プライム・ペア」問題解説... 問題のおさらい 自然数 k に対し、1 から k までの自然数のうち k と互いに素なものの個数を F(k) と定義します。 (F(k) はオイラーのφ関数とも呼ばれています。参考:オイラーのφ関数(Wikipedia)) 例えば F(12)=4 です。1 から 12 のうち 12 と互いに素...
【謎解きプログラム】データベースを扱ってみよう【SQLite】解答と解説... 【謎解きプログラム】データベースを扱ってみよう【SQLite】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 ...
【謎解きプログラム】弾幕の軌跡を作ってみよう【描画】解答と解説... 【謎解きプログラム】弾幕の軌跡を作ってみよう【描画】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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