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

■関連記事

「放物線とマス目の関係」問題の解答と解説... 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時間...
数学の問題をプログラミングで解こう!「ルーム・アンド・ルーフ」問題解説... 問題のおさらい 一辺の長さが 1 の正方形を考えます。これを P0 と呼びます。 各頂点を時計回りに A, B, C, D とします。 P0 に対し、次の手順で新しい正方形を描きます。 辺 BC と同じ辺を持つ正三角形 BCE を P0 の外側に描きます。 D と E を線分で結びます。 そして...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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