C++で素数列挙！エラトステネスの篩 編
C++で素数列挙！O( N√N )編 を書きましたが、
今度はもっと高速な エラトステネスの篩(ふるい)編 *1 を書いたのでコードを残します。
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; #include <vector> std::vector<int> Eratosthenes( const int N ) { std::vector<bool> is_prime( N + 1 ); for( int i = 0; i <= N; i++ ) { is_prime[ i ] = true; } std::vector<int> P; for( int i = 2; i <= N; i++ ) { if( is_prime[ i ] ) { for( int j = 2 * i; j <= N; j += i ) { is_prime[ j ] = false; } P.emplace_back( i ); } } return P; } int main() { int N; cin >> N; for( const auto &x: Eratosthenes( N ) ) { cout << x << " "; } return 0; }
ベースは 蟻本 P112 の「素数の個数」を求めるというコードです。
上記コードは、素数を pick upして vector に格納すると云うものです。
計算量はO( N log log N )だそうです。(蟻本 P112より)
C++で素数列挙！O( N √N )編
以前、C++で素数判定！を書いたのですが、
今回は C++で素数列挙！O( N √N ) のコードを書いたのでメモとして残します。
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int N; vector<int> P; void prime( const int N ) { for( int i = 2; i <= N; i++ ) { bool flag = true; for( int j = 2; j * j <= i; j++ ) { if( i % j == 0 ) { flag = false; break; } } if( flag ) { P.emplace_back( i ); } } } int main() { cin >> N; prime( N ); for( const auto &x: P ) { cout << x << " "; } return 0; }
N - 1個の自然数の中から素数だけ Pick upして vector に格納後、main関数内で出力しています。*1
計算量は、O( N )個の数に対して O( √N ) 時間かけて探索するので O( N √N ) です。
Sum of Integers｜AOJ｜深さ優先探索(DFS)
深さ優先探索(DFS)を勉強中で、DFSを使って解ける優しめ問題という事で、
整数の和 | Aizu Online Judge を解きました。
＜題意＞
0 〜 9 の数字から異なる数をN個取り出して、和がSとなる組み合わせが何個あるか出力する
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; // i --> 0 - 9までの数字 // sum --> 合計値 // cnt --> 和がSとなる組み合わせの数 // total --> 足す数(N個まで足す) int N, S, cnt; void dfs( int i, int sum, int total ) { //N回を満たしている 且つ 合計がSに達したものをcountする if( total == N && sum == S ) { cnt++; return; } //0-9まで探索したら or 足す回数がN回に達したら 終わり if( i == 10 || total == N ) return; //合計に i を足す場合 -> 足す回数を +1 する dfs( i + 1, sum + i, total + 1 ); //合計に i を足さない場合 dfs( i + 1, sum, total ); } int main() { while( cin >> N >> S ) { if( N == 0 && S == 0 ) break; //合計値の初期化 cnt = 0; //dfs( 数字の0から, 合計値0から, 足す数字0から) dfs( 0, 0, 0 ); cout << cnt << endl; } return 0; }
DFSを本で勉強したのですが、さっぱり実装出来る気がしなくて、
処理をいくつかに分割して書いてやっとまとまりました。
手順としては下記の工程を経ています。
1）足し算部分の再帰を書く
2）合計を取る部分を書く
3）合計がSとなったものをcountする部分を書く
4）合計に足す場合と、足さない場合を書く
5）N個だけ選んで和を取る部分を書く
個々の処理がどうなっているか良く解ったので理解が進みました。
この問題を解く際、グローバル変数に count と云う変数名を使ったら gccに怒られました。
std::count と区別がつかないよって事らしいです。
それから、returnで何も返さない関数はvoidで宣言する様で、そこも新たに覚えました。
(何も返さない関数を初めて書きました...！)
次はstack編も覚えなくてはみたいな感じです。
ICPCOOC 2016 - A Rearranging a Sequence｜AOJ
ICPCOOC2016 - A Rearranging a Sequence を解きました。
＜題意＞
・N個の整数の中から、M個の整数を移動(TOPに積む)する。
・移動する整数M個は e[ i ] で与えられる。
・移動後の並びを出力する。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) #define ALL(x) begin(x),end(x) struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N, M; cin >> N >> M; vector<int> A( M ); for( auto &&x : A ) { cin >> x; } vector<int> num; REP( i, N ) { num.emplace_back( i + 1 ); } REP( i, M ) { auto index = distance( begin( num ), find( ALL( num ), A[ i ] ) ); num.erase( begin( num ) + index ); num.insert( begin( num ), A[ i ] ); } for( const auto &x : num ) { cout << x << endl; } return 0; }
↑ 一番初めに提出したコード、TLE...
計算量考えてちゃんと実装しようね、って事で、計算量の勉強をしつつ考察をし直しました。
この問題をTLEしない為には O( 1 ) か O( log ) にする必要があるのですが、
std::vector で insert, erase の処理をしてしまうと、それぞれ O( n ) になってしまい間に合いません...。なので insert, erase での実装は諦めました。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(n); i++) #define REP2(i,x,n) for(int i=x; i<(n); i++) #define ALL(x) begin(x),end(x) using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N, M; cin >> N >> M; vector<int> e( M ); for( auto &x : e ) { cin >> x; } reverse( ALL( e ) ); vector<int> vc; REP( i, M ) { if( count( ALL( vc ), e[ i ] ) < 1 ) { vc.emplace_back( e[ i ] ); } } for( const auto &x : vc ) { cout << x << endl; } sort( ALL( vc ) ); REP2( i, 1, N ) { if( count( ALL( vc ), i ) == 1 ) { continue; } cout << i << endl; } return 0; }
↑ 2回目の提出！色々計算量を調べて書きました！！...TLE...
？？？？？となったのですが、計算量の調べ方が悪かった様です...。
algorithm ヘッダの count *1 ではなくて、 set::count *2 の計算量を参照していました...。
( 以前も同様の参照ミスをした事があって気を付けてはいたのですが... )
そんな訳でまた考え直し ➡︎ 計算量 O( 1 ) ってもう配列参照ぐらいしか出来ないと知る...。
配列参照で何が出来るんですか、となった ➡︎ 出来るっぽい
if の中の count がしていた事は、重複がある値を除く事。
なので、重複する値をもう1つ別の配列で持って管理＆参照する方針でコード書きました。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(n); i++) #define REP2(i,x,n) for(int i=x; i<(n); i++) #define ALL(x) begin(x),end(x) using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; int main() { int N, M; cin >> N >> M; vector<int> e( M ); for( auto &x : e ) { cin >> x; } reverse( ALL( e ) ); //move vector<int> flag( N + 1 ); REP( i, M ) { if( !flag[ e[ i ] ] ) { cout << e[ i ] << endl; flag[ e[ i ] ] = 1; } } //not move REP2( i, 1, N + 1 ) { if( !flag[ i ] ) { cout << i << endl; } } return 0; }
↑ 3回目の提出で 計算量の問題をクリアして AC できました。
計算量を落とす作業がかなり大変でした...(普段全く意識した事がなかったので)
これからは制約関係なく、計算量を意識してコード書こうと思いました。
注）記事の中の計算量違っていたらこっそり教えて下さい。
cpp macro template - 2 -
型で事故り、マクロtemplateを修正したのでメモ。
out #define SORT(x) sort((x).begin(),(x).end(),greater<int>()) out #define SORTP(x) sort((x).begin(),(x).end(),greater<pair<int,int>>()); in #define SORTR(x) {sort(begin(x),end(x));reverse(begin(x),end(x));}
