CodeIQ 三角形は何通り?
今日は以下の問題を解いてみました。
――――――――――――――――――――――――――――――――――――――――――
【問題】
入力nに対して
(はすべて整数)を満たすの中で、
これらを3辺とする三角形が成り立つ場合の組み合わせを求めるプログラムを書いてください。
【入力】
標準入力から、整数が与えられます。
【出力】
標準出力に、条件を満たす組み合わせの総数のみを出力してください。
――――――――――――――――――――――――――――――――――――――――――
まずは何も考えずにとなる組み合わせを全て調べてみます。
//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(^Д^)プギャー」と弾かれました。
それもそのはずで、計算量はとなってしまい
n=1,000,000の場合、到底1秒以内で答えを出せそうもありません。
もっと良いアルゴリズムを考えないといけないわけです。
まずはc=nの場合で全部の組み合わせを樹形図にしてみます。
となる組み合わせは、
のとき、の通り
のとき、の通り
のとき、の通り
※ただし、(は切り捨て)ならば、
・cが奇数ならばの通り
・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; }
CodeIQ 実力判定問題:Cランク
初投稿です。
日本語があまりにもうまく使えないので
文章的におかしい部分もたくさんあるかもしれませんが
よろしくお願いします。
まだまだプログラミングのことは勉強中なのです。
いろいろとやっていきたいです。
あと、本日20歳の誕生日でした。
酒が飲めるようになりました。
CodeIQの実力判定問題を後輩がやっていたので私もやってみました。
―――――――――――――――――――――――――――――――――――――――
【問題】
いくつかの整数値が与えられます。
それらの中で、和がちょうど256になるような2数が
存在するかどうかを調べてください。
【入力】
標準入力から、整数値が与えられます。
1行目は整数値N、
2行目はN個の整数値Akが半角スペースで区切られています。
【出力】
和が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; }
ちなみに計算量はです。
今回の問題ではであるため
でも十分ですが計算量を少なくするために改良してみます。
改良版アルゴリズム
①与えられた数値をクイックソートを用いてソート。
②配列の要素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; }
計算量は
クイックソートの部分は
探索の部分はcount - cpprefjp C++日本語リファレンスより
std::countの計算量はであるが
要素が128の場合の探索は0回または1回しか行わない。
したがって、ステップ数は
①128の要素が含まれていた場合、
②128の要素が含まれていない場合、
であるため計算量はとなります。
計算量から見ると愚直に組んだのよりはよくなりました(たぶん)
最後の計算量の考察は厳密にあってるのかよくわかんないですが
実行結果が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