CodeIQ MAGAZINECodeIQ MAGAZINE

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

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

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

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

等式を成立させるようなプラスマイナスの入れ方の数を求める問題です。
素朴に解こうとすると膨大な計算量を要しますが、うまく計算量を抑えられたでしょうか?
ぜひ出題者の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
  • このエントリーをはてなブックマークに追加

■関連記事

【謎解きプログラム】この処理は?【コードを読もう】解答と解説... 【謎解きプログラム】この処理は?【コードを読もう】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以...
数学の問題をプログラミングで解こう!「ループ・トラッキング」問題解説... 問題のおさらい 自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。 例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。 さて、整数 k(0 ≦ k ≦ n)に対して、関数 Fn による変換を繰り返し行い...
【謎解きプログラム】どんな結果になる?【アロー関数】解答と解説... 【謎解きプログラム】どんな結果になる?【アロー関数】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
数学の問題をプログラミングで解こう!「カウント・スリー」問題解説... 問題のおさらい 自然数を 1 から順に書き並べていきます。 このとき、3 の数字が現れる回数を数えます。 自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。 例えば F(10)=35 です。 下の通り、10 個目の 3 は、35 を書いて...
【息抜き】カードを上手く並べよう【言語不問】解答と解説... 【息抜き】カードを上手く並べよう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 あなたは、11から99までの、89枚のカードを持っています。問題では、横幅と高さの整数が与えられます。この横幅と高さで作られるマス...
【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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