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
  • このエントリーをはてなブックマークに追加

■関連記事

【夏のミステリー】殺人現場のコード 解答と解説... 【夏のミステリー】殺人現場のコード 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 殺人現場にプログラマが倒れていて、途中までプログラムが書かれている。 「続きを書いて欲しい」 これはダイイングメッセージなのか? どう...
数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説... 問題のおさらい n 個のキャンディをグループに分けます。 グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。 例えば、F(8, 3)=5 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...
【夏のミステリー】時間制限の密室 解答と解説... 【夏のミステリー】時間制限の密室 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 (なんやかんやあって)命からがら逃げてきた、あなた。 しかし逃げ込んだ部屋にあなたが入った途端、自動でドアはロックされ、しかも10分後にはガ...
数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説... 問題のおさらい n 本の丸太があります。これらの向きと端をそろえ、地面に積みます。 積む際には次のルールに従います。 地面には好きな本数の丸太を置けます。隣り合う丸太は接して置きます。 左右に隣り合う 2 本の丸太の上に、新たな丸太を 1 本置けます。 全ての丸太は一...
【息抜き】平均値と中央値【言語不問】解答と解説... 【息抜き】平均値と中央値【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行(最大行数30)は、半角数字のみの整数(最大桁数8)になっています。 この各行の平均値と中央値を求めて下さい。小...
【息抜き】右位置揃え【言語不問】解答と解説... 【息抜き】右位置揃え【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行は、半角数字のみの整数(最大桁数32)になっています。 この各行の先頭に任意の数の半角のアンダーバー(_)を挿入して...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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