CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。

等式を成立させるようなプラスマイナスの入れ方の数を求める問題です。
素朴に解こうとすると膨大な計算量を要しますが、うまく計算量を抑えられたでしょうか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックしてください!
by CodeIQ運営事務局

問題のおさらい

自然数 n に対して、次の等式を考えます。

    □1□2□3□4…□n = 0

四角の部分には、プラス(+)またはマイナス(-)の記号が入ります。

等式を成立させるような記号の入れ方を考えましょう。

例えば、n = 7 のとき、次の 8 通りの入れ方が可能です。

  • +1+2-3+4-5-6+7 = 0
  • +1+2-3-4+5+6-7 = 0
  • +1-2+3+4-5+6-7 = 0
  • +1-2-3-4-5+6+7 = 0
  • -1+2+3+4+5-6-7 = 0
  • -1+2-3-4+5-6+7 = 0
  • -1-2+3+4-5-6+7 = 0
  • -1-2+3-4+5+6-7 = 0

自然数 n に対し、等式を成立させる記号の入れ方の数を F(n) と定義します。

例えば F(7) = 8 です。

同様に、F(3) = 2、F(8) = 14 となることが確かめられます。

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

方針

等式を成立させる記号の入れ方の数を求める問題です。

ぱっと思いつく解法は、記号の入れ方の全てのパターンを列挙して、左辺がゼロになるかどうかを確かめるというものです。しかし、本問では n の上限が 50 ですから、全ての組み合わせは 250 ≒ 1015 通りです。あまりに膨大な数ですので、他のアプローチをとらねばなりません。

そこで、次の G(n, s) を新たに定義しましょう。

  G(n, s) : □1□2□3□4…□ns となる記号の入れ方の数.

G(n, s) は、F(n) をより一般化したものです。s = 0 とした G(n, 0) が、求めるべき F(n) です。

さて、G(n, s) を求めるにはどうすればよいでしょうか。ここで役に立つ考え方が、一つ手前の状態を考えることです。ここでいう一つ手前の状態とは、n の一つ前、つまり n-1 までの部分を指します。すべての s に対する G(n-1, s) の値が分かっていたとして、これらの値を用いて G(n, s) を表せないだろうか? と考えてみましょう。要するに、G(n, s) の漸化式を導出することが、本問を解くポイントです。

そこで、G(n, s) の値を、□1□2□3□4…□(n-1)□n の最後の□にプラスとマイナスのどちらが入るかで場合分けしてみましょう。プラスの場合は、n-1 までの部分 □1□2□3□4…□(n-1) が sn に等しければ、全体は s に等しくなります。そのような記号の入れ方は G(n-1, sn) 通りです。一方、最後の□がマイナスの場合は、n-1 までの部分が s+n に等しければ、全体は s に等しくなります。そのような記号の入れ方は G(n-1, s+n) 通りです。結局のところ、G(n, s) とはこのいずれかですから、G(n, s) = G(n-1, sn) + G(n-1, s+n) という漸化式が導き出せます。

あとは、漸化式を解くコードを書けばOKです。さまざまな s に対する G(n, s) の値を保存するためのデータ構造を用意します。n = 0 の場合の G(n, s) の値は、s = 0 のときのみ 1、それ以外では 0 です。これらを初期値として、n についてのループ文を書き、保存された値を次々と更新していきましょう。

コード例は以下です(C++)。G(n, s) の値を std::map で保存しています。s の正負がひっくり返っても G(n, s) の値が変わらないことを利用し、s が負のときの計算を省いています。

#include <iostream>
#include <map>
#include <cstdlib>
using namespace std;

int main()
{
    int n;
    cin >> n;
    map<int, long long> d, d_new;
    d[0] = 1;
    for (int i = 1; i <= n; i++) {
        int s_max = i * (i + 1) / 2;
        for (int s = 0; s <= s_max; s++) {
            d_new[s] = d[abs(s - i)] + d[s + i];
        }
        d.swap(d_new);
    }
    cout << d[0] << endl;
}

みんなのコード

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

CodeIQ「プラス・マイナス・ゼロ」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

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

■関連記事

【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...
数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説... 問題のおさらい 自然数 n と素数 p に対し、n の階乗(n!)を p でこれ以上割り切れなくなるまで繰り返し割り、その商をさらに p で割ったときの余りを F(n, p) と定義します。 例えば F(12, 5)=4 です。 12!(=479001600)は 5 で最大 2 回割ることができ...
【息抜き】ファイル名を作ろう【言語不問】解答と解説... 【息抜き】ファイル名を作ろう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 ファイルをディレクトリ内に作成する際、同じ名前のファイルがあると、末尾に数字を付けるなどして同じ名前にならないようにします。 こうし...
【夏のミステリー】殺人現場のコード 解答と解説... 【夏のミステリー】殺人現場のコード 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 殺人現場にプログラマが倒れていて、途中までプログラムが書かれている。 「続きを書いて欲しい」 これはダイイングメッセージなのか? どう...
数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説... 問題のおさらい n 個のキャンディをグループに分けます。 グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。 例えば、F(8, 3)=5 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...
【夏のミステリー】時間制限の密室 解答と解説... 【夏のミステリー】時間制限の密室 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 (なんやかんやあって)命からがら逃げてきた、あなた。 しかし逃げ込んだ部屋にあなたが入った途端、自動でドアはロックされ、しかも10分後にはガ...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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