ゆずねのあとりえ  ~Atelier of Yuzune~

プログラミングの勉強記録を残したり。ゲームの感想書いたり日記書いたり。

CodeIQ 三角形は何通り?

今日は以下の問題を解いてみました。

codeiq.jp

――――――――――――――――――――――――――――――――――――――――――
【問題】
入力nに対して
1\leq a \leq b\leq c \leq na, b, c, nはすべて整数)を満たすa, b, cの中で、
これらを3辺とする三角形が成り立つ場合の組み合わせを求めるプログラムを書いてください。

【入力】
標準入力から、整数n(1 \leq n \leq 1000000)が与えられます。

【出力】
標準出力に、条件を満たす組み合わせの総数のみを出力してください。
――――――――――――――――――――――――――――――――――――――――――

まずは何も考えずに1\leq a \leq b\leq c \leq nとなる組み合わせを全て調べてみます。

//CodeIQ 三角形は何通り?:愚直に全探索
#include<iostream>
using namespace std;

int64_t solve(const int n) {
	int64_t count = 0;
	for (int c = n;c >= 1;c--) {
		for (int b = c;b >= 1;b--) {
			for (int a = b;a >= 1;a--) {
				if (a + b > c) {
					count++;
				}
			}
		}
	}
	return count;
}

int main() {
	int n;
	cin >> n;

	cout << solve(n) << endl;
	
	return 0;
}

とりあえず1回提出してみたところ
「時間かかりすぎや、出直してこいm9(^Д^)プギャー」と弾かれました。

それもそのはずで、計算量はO(n^3)となってしまい
n=1,000,000の場合、到底1秒以内で答えを出せそうもありません。

もっと良いアルゴリズムを考えないといけないわけです。

まずはc=nの場合で全部の組み合わせを樹形図にしてみます。
f:id:AtelierOfYuzune:20160905181312p:plainf:id:AtelierOfYuzune:20160905181341p:plainf:id:AtelierOfYuzune:20160905181339p:plainf:id:AtelierOfYuzune:20160905181340p:plainf:id:AtelierOfYuzune:20160905181830p:plain

a+b>cとなる組み合わせは、
b=n のとき、a=n,n-1,n-2,\cdots,1n通り
b=n-1のとき、a=n-1,n-2,\cdots,2n-2通り
b=n-2のとき、a=n-2,n-3,\cdots,3n-4通り

※ただし、b=\frac{n}{2} + 1\frac{n}{2}は切り捨て)ならば、
・cが奇数ならばa=\frac{n}{2} + 11通り
・cが偶数ならばa=\frac{n}{2} + 1,\frac{n}{2}2通り

の総和(ただし2b>cの場合のみ)となります。

この総和をS_nと置くことにします。

c=1のとき、b = 1 (= \frac{1}{2} + 1) よりS_1=1
c=2のとき、b = 2 (= \frac{2}{2} + 1) よりS_2=2
c=3のとき、b = 3 , 2(=\frac{3}{2} + 1)よりS_3= 3+1=4
c=4のとき、b = 4 , 3(=\frac{4}{2} + 1)よりS_4= 4+2=6

となります。カッコ内の分数は全て切り捨てです。

これを並べてみると
S_1=1
S_2=2
S_3=3+1=3+S_1
S_4=4+2=4+S_2
S_5=5+3+1=5+S_3
S_6=6+4+2=6+S_4
となり、漸化式で表すことができます。

よって、一般項は
S_k=S_{k-2}+k
と表すことができます。

これをc=1からc=nまでの総和を求めればよいので、
三角形は\Sigma_{c=1}^n S_c通りとなります。

後はこれをプログラムで実装すればいいのです。
※solve関数以外の場所は書き換えておりません。

int64_t solve(const int n) {
	int64_t count = 0;
	int64_t sum_o = 0, sum_e = 0;
	for (int i = 1;i <= n;i++) {
		if ((i & 1) == 0) {
			sum_o += i;
			count += sum_o;
		}
		else {
			sum_e += i;
			count += sum_e;
		}
	}
	return count;
}

このようにすることでO(n^3)だったアルゴリズム
O(n)アルゴリズムに改良することができました。

CodeIQ 実力判定問題:Cランク

初投稿です。
日本語があまりにもうまく使えないので
文章的におかしい部分もたくさんあるかもしれませんが
よろしくお願いします。

まだまだプログラミングのことは勉強中なのです。
いろいろとやっていきたいです。

あと、本日20歳の誕生日でした。
酒が飲めるようになりました。


CodeIQの実力判定問題を後輩がやっていたので私もやってみました。

codeiq.jp

―――――――――――――――――――――――――――――――――――――――
【問題】
いくつかの整数値が与えられます。
それらの中で、和がちょうど256になるような2数が
存在するかどうかを調べてください。

【入力】
標準入力から、整数値が与えられます。
1行目は整数値N(2 \leq N \leq 100)
2行目はN個の整数値Ak(0 \leq Ak \leq 256)が半角スペースで区切られています。

【出力】
和が256になる2数が存在する場合は"yes"、
存在しない場合は"no"と、標準出力に出力してください。
―――――――――――――――――――――――――――――――――――――――

まずは愚直に組んでみました。

//CodeIQ 実力判定問題 Cランク:愚直に組んでみた
#include<iostream>
#include<vector>
using namespace std;

void input(const int n,vector<int> &elem) {
	elem.resize(n);
	for (int i = 0;i < n;i++) {
		cin >> elem[i];
	}
}

bool search(const int &n,const vector<int> &elem) {
	for (int i = 0;i < n - 1;i++) {
		for (int j = i + 1;j < n;j++) {
			if (elem[i] + elem[j] == 256) {
				return true;
			}
		}
	}
	return false;
}

int main() {
	vector<int> elem;
	int num;
	cin >> num;
	
	input(num, elem);
	if (search(num, elem)) {
		cout << "yes" << endl;
	}
	else {
		cout << "no" << endl;
	}

	return 0;
}

ちなみに計算量はO(n^2)です。
今回の問題では2 \leq N \leq 100であるため
O(n^2)でも十分ですが計算量を少なくするために改良してみます。

改良版アルゴリズム
①与えられた数値をクイックソートを用いてソート。
②配列の要素1つ1つに対して足して256になる対の数値を二分探索で探す。
 配列内の要素が128であった場合は128が2つ以上あるかどうかを調べる

//CodeIQ 実力判定問題 Cランク:改良してみた
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void input(const int n,vector<int> &elem) {
	elem.resize(n);
	for (int i = 0;i < n;i++) {
		cin >> elem[i];
	}
}

bool search(const int &n,const vector<int> &elem) {
	for (int i = 0;i < n;i++) {
		if (elem[i] == 128) {
			if (count(elem.begin(), elem.end(), 128) >= 2) {
				return true;
			}
		}
		else {
			if (binary_search(elem.begin(), elem.end(), 256 - elem[i])) {
				return true;
			}
		}
	}
	return false;
}

int main() {
	vector<int> elem;
	int num;
	cin >> num;
	
	input(num, elem);
	sort(elem.begin(), elem.end());

	if (search(num, elem)) {
		cout << "yes" << endl;
	}
	else {
		cout << "no" << endl;
	}

	return 0;
}

計算量は
クイックソートの部分はO(n \log n)
探索の部分はcount - cpprefjp C++日本語リファレンスより
std::countの計算量はO(N)であるが
要素が128の場合の探索は0回または1回しか行わない。

したがって、ステップ数は
①128の要素が含まれていた場合、 1 \times n + (n - 1) \log n
②128の要素が含まれていない場合、n \log n
であるため計算量はO(n \log n)となります。

計算量から見ると愚直に組んだのよりはよくなりました(たぶん)

最後の計算量の考察は厳密にあってるのかよくわかんないですが
実行結果がnoとなる場合となるように乱数を生成し
データ数N=1000,5000,10000,50000,100000,500000の6つで
計算時間をはかってみました。

改良前[ms] 改良後[ms]
1000 1 1
5000 17 1
10000 61 2
50000 1490 6
100000 6096 13
500000 300000以上 67

結果からみても高速なアルゴリズムになってるといえます。
やっぱりアルゴリズムって大事なんだなぁとつくづく実感しました(こなみ)

今日はここまでにしてオメガラビリンスが最後まで攻略できてないので
それをやりましょうかね…
見た目とは裏腹にゲーム性もあってオススメです。
www.d3p.co.jp