「プラス・マイナス・ゼロ」問題

概要

CodeIQ で私の解いてた問題で、ブログネタにできそうなものがあったので記述。

課題内容

codeiq.jp

自然数 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) の値を出力するプログラムを書いてください。

回答(C言語)

まずは、私の回答。

#include<stdio.h>

int main() {
	int i, j, n;
	scanf("%d", &n);

	int allSum = n*(n+1) >> 1;
	if(allSum & 1) {
		printf("0");
		return 0;
	}
	long long int count[allSum+1];
	for(i=0; i<=allSum; i++) count[i]=0L;

	count[0] = 1L;
	for(i=1; i<=n; i++) {
		int prevLength = ((i-1)*i >> 1)+1;
		long long int copy[prevLength];
		for(j=0; j<prevLength; j++) copy[j] = count[j];
		for(j=0; j<prevLength; j++) count[i+j] += copy[j];
	}
	printf("%lld", count[allSum >> 1]);
	return 0;
}

一部シフト演算子とか、ビット演算子とか気持ち悪いものを使っているが、次と同値。(読み辛くて申し訳ない)

• [式] >> 1 の部分 →　[式]/ 2
• [式] & 1 →　[式]が奇数なら1、偶数なら0

言い訳：当初書いたアルゴリズムがひどくて、計算が時間内に終わらず、できる限り計算時間の少なさそうな方法を選んていたから。

説明

単純にやると・・

回答の解説を見て頂ければ分かると思うが、単純に問題を解くと私の環境では n=23 くらいで処理が1秒以内に終了しなくなった。

なお、ここで単純な処理とは各□に+ や - を全組み合わせを試して確認するという方法。
この方法でも正しい結果は論理的に得られるが、アルゴリズムとしては n が 1増加することによって
計算時間が2倍増加してしまうため、アルゴリズムとしては実用的なものではない。

そういうわけで、確認方法を多少工夫する必要があり、その基本方針はまさに回答の「一つ手前の状態を考える」。
私はまず問題を変換してから考えているため、まずそれから説明する。

問題変換

全部のプラスマイナスパターンを確認するのは、面倒なので、まず問題を変換して解きやすくする。

まず、□1□2□3□4…□n ＝ 0　を満たすプラスマイナスの組が合計 0 になる状況では、何が起こるか？

1〜n のプラス集合とマイナス集合の各々の合計値の絶対値は一致する
(例：＋1＋2－3＋4－5－6＋7 ＝ 0　→　|1+2+4+7| = |-3-5-6|=14
　↓
各々の集合の絶対値は、1〜n の和の半分に相当する
(例：1+2+3+4+5+6+7 = 7*8/2 = 28,　上記絶対値は14)
　↓
1〜n のうち任意集合の合計値が になる組み合わせ数が求めるべき数
　↓
発生しうる任意集合の和とその組み合わせの数をリスト化したものを作成
　↓
最後にの組み合わせの数を表示

ただし、n=2 のように が奇数になるものは解が存在しないため除外が必要。
これを下記で行っている。

	int allSum = n*(n+1) >> 1;
	if(allSum & 1) {
		printf("0");
		return 0;
	}

前回の処理結果から次の結果を求める方法

まず、選択した組み合わせの和を配列のインデックスに、その組み合わせ数を配列の値とする。
入力 n から、組み合わせ数を格納する配列長は、0(全て選択しない)〜 (全て選択)まで確保すれば良い。

	long long int count[allSum+1];
	for(i=0; i<=allSum; i++) count[i]=0L;

まず、簡単な例を考える。□1 = 0 の場合。発生する部分和とそのカウント数は次の２通り。

[集合の合計値]	[組み合わせ数]
0	1
1	1

ここで、新しく２を追加する。つまり、 □1□2= 0 の場合。

[集合の合計値]	[これまでの組み合わせ数]	[2を選択した組み合わせ]	[組み合わせ数]
0	1	-	1
1	1	-	1
2	-	1	1
3	-	1	1

次に3を含めた場合。

[集合の合計値]	[これまでの組み合わせ数]	[3を選択した組み合わせ]	[組み合わせ数]
0	1	-	1
1	1	-	1
2	1	-	1
3	1	1	2
4	-	1	1
5	-	1	1
6	-	1	1

同様に4を含めた場合。

[集合の合計値]	[これまでの組み合わせ数]	[4を選択した組み合わせ]	[組み合わせ数]
0	1	-	1
1	1	-	1
2	1	-	1
3	2	-	2
4	1	1	2
5	1	1	2
6	1	1	2
7	-	2	2
8	-	1	1
9	-	1	1
10	-	1	1

これを以下のようにまとめる。

[集合の合計値]	[選択なし]	[1選択]	[2選択]	[3選択]	[4選択]	[組み合わせ数]
0	1	-	-	-	-	1
1	-	1	-	-	-	1
2	-	-	1	-	-	1
3	-	-	1	1	-	2
4	-	-	-	1	1	2
5	-	-	-	1	1	2
6	-	-	-	1	1	2
7	-	-	-	-	2	2
8	-	-	-	-	1	1
9	-	-	-	-	1	1
10	-	-	-	-	1	1

この表から、これまでの組み合わせ結果が分かれば、その結果と「それを下にn個ずらした組み合わせ数」を加算すれば組み合わせ数が求まる。
あとは、これを実装すれば良い。これを行ってるのが以下。

	count[0] = 1L;
	for(i=1; i<=n; i++) {
		int prevLength = ((i-1)*i >> 1)+1; // 前回には、どの範囲までを対象にすればいいか
		long long int copy[prevLength];
		for(j=0; j<prevLength; j++) copy[j] = count[j]; // 値のコピー
		for(j=0; j<prevLength; j++) count[i+j] += copy[j]; // 追加分足し込み
	}

そして、最終的に欲しい組み合わせ数は、1〜nまでの合計/2 だから。

	printf("%lld", count[allSum >> 1]);

で表示している。

改良点

コピーする必要なし

書いているとき気づいたが、値のコピーを作成するロジックは必要はない。(下記3, 4行目)

	for(i=1; i<=n; i++) {
		int prevLength = ((i-1)*i >> 1)+1; // 前回には、どの範囲までを対象にすればいいか
		long long int copy[prevLength];
		for(j=0; j<prevLength; j++) copy[j] = count[j]; // 値のコピー
		for(j=0; j<prevLength; j++) count[i+j] += copy[j]; // 追加分足し込み
	}

このコピーは、値が2重に足し込まれる問題に対して回避するため、元の値を保持する目的で作成していた。
しかし、この現象はインデックスが小さいものから処理すると発生するが、大きいものから処理すれば起こらない。

	for(i=1; i<=n; i++) {
		int prevLength = (i-1)*i >> 1; // 前回には、どの範囲までを対象にすればいいか
		long long int copy[prevLength];
		for(j=prevLength; j>=0; j--) count[i+j] += copy[j]; // 追加分足し込み
	}

この方がシンプルになる。

配列の初期化

	long long int count[allSum+1];
	for(i=0; i<=allSum; i++) count[i]=0L;
	count[0] = 1L;

配列の初期化は、こんなのでも可能らしく、値が指定されていないと0が自動で入るらしい。
そう思って、下記のように修正・・・。

	long long int count[allSum+1] = {1};

・・と思ったら、これ変数だめなようで、この書き方はサイズを定数で書いて確実にその長さが
存在することを保証しないといけないみたいだ。仕方ないので、n<=50 まで対応 → 50*51/2+1 = 1276 にすることに。

	long long int count[1276] = {1};

おまけ：短いコード

短いコードにするなら、ここまでは小さくできた。

#include<stdio.h>
int main() {
        int n,i=0,j;
        scanf("%d", &n);
        long long a=n*(n+1)/2,c[1276]={1};
        for(;++i<=n;)for(j=a;j>=0;j--)c[i+j]+=c[j];
        printf("%lld",a&1?0:c[a/2]);
}

不要な改行コードとかとって・・

#include<stdio.h>
int main(){int n,i=0,j;scanf("%d",&n);long long a=n*(n+1)/2,c[1276]={1};for(;++i<=n;)for(j=a;j>=0;j--)c[i+j]+=c[j];printf("%lld",a&1?0:c[a/2]);}

163byte。多分、やり方を変更すれば、もうちょっと縮まるかなあ。