ブログ閉鎖します

もうすぐ受験生ということもあり、ブログを閉鎖します。

閉鎖……というよりも放置?

本当に閉鎖すると、過去の記事が見れなくなっちゃいますので放置です。

とりあえず受験勉強頑張ります。
スポンサーサイト

【数学オリンピック 2013 予選】 (7) 解法

20130115_1.png


x[1],x[2],x[3]...x[25]の値を、
1111100000111110000011111
のように表現します。(x[1]=1,x[2]=1,x[3]=1,x[4]=1,x[5]=1,x[6]=0...の場合)

また0-1-0-1-0という表現は、xが
0000011111000001111100000
のような数字の並びであることを表現することとします。
例えば
0111111111000000000000010
0000000000011110001110000
0100000000000000000000010
全て0-1-0-1-0です。

二項の差が0または1、
最初、最後それぞれ0または1ということを考えると、
0-1-2-0
2-1-2
0-2-0
などはありえないことが分かります。
また1-x-1の場合
最初と最後が1、二項の差が1である箇所が2つあるため4となります。
つまり(最初の項)+(最後の項)+(二項の差が1の箇所の数)=4を満たすパターン数を求めればいいみたいです。

ここから、和が4となる組み合わせは、
0-1-0-1-0
0-1-2-1-0
0-1-0-1
0-1-2-1
1-0-1-0
1-2-1-0
1-0-1
1-2-1

の8パターンが存在することが分かります。
変化点を24個の中から変化箇所を選べばいいので、上から順に
24C4
24C4
24C3
24C3
24C3
24C3
24C2
24C2
であることが分かります。互いに排反なので、求める値は
2*24C2+4*24C3+2*24C4=29900
となります。

<組み合わせの総数>
●|●|●|○|○|○|●|●|●
9個あって●-○-●となる組み合わせの総数を考えると、
二項の間は8つあるので、8個の間から2つ選ぶ場合(=8C2)の数と等しくなります。

●|●|●|○|○|○|●|●|●|○|○|○|
12個あって●-○-●-○となる組み合わせの総数を考えると、
二項の間は11個あるので、11個の間から3つ選ぶ場合の数(=11C3)と等しくなります。

【数学オリンピック 2013 予選】 (10) 解法プログラム

もう操作がよくわからなくなった。これガウスの値って同じの出てこないんですかね?
一応重複してる可能性を考えて、コーディングしてますけど。

プログラムによると793が答えみたいです(自信無)。
#include <iostream>

#define N 2013

using namespace std;

int main() {
	// 表向きtrue、裏向きfalse
	bool *a = new bool[N];
	bool *mask = new bool[N];

	for (int i = 0; i < N; i++) {
		a[i] = false;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < N; j++) {
			mask[j] = false;
		}

		for (int j = 0; j <= i - 1; j++) {
			if ((N * j) / i < N) {
				mask[(N * j) / i] = true;
			}
		}

		for (int j = 0; j < N; j++) {
			if (mask[j]) {
				a[j] = !a[j];
			}
		}
	}

	int sum = 0;

	for (int i = 0; i < N; i++) {
		sum += (a[i]) ? 1 : 0;
	}

	cout << sum << endl;

	delete[] a;
	delete[] mask;

	while (true) {}
}

暫くC#使っていると、bool型をキャストするのにためらいがでてきますね。三項演算子で変換してます。
そもそも問題をよく理解してないので、答えがあってるか微妙。
コードを見て合ってるか判断してください。

プログラミングって便利ですね……、つくづくそう思います。
ていうかこの問題自体プログラミングしやすいように作られているような。

ループの値の範囲が間違ってたのと、(N*j)/iで不正アクセスが起きるのを修正しました。
その結果解答は別の値に。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。