CodeIQ 実力判定問題：Cランク - 　ゆずねのあとりえ　~Atelier of Yuzune~

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

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

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

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

―――――――――――――――――――――――――――――――――――――――
【問題】
いくつかの整数値が与えられます。
それらの中で、和がちょうど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