Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@tharashi

競技プログラミング(C++)で最初に学ぶ基本コード10個

Last updated at Posted at 2020-02-18

#要旨

  • 競技プログラミングでよく使うC++について10個
  • プログラミング基礎(初心者向け)

#はじめに
本稿では競技プログラミング(以下:「競プロ」)で頻繁に用いるコードについて備忘録的な位置付けでメモにしました。個人的にはC++は組み込み系でよく使われるイメージですが競プロではメインストリームだと思います。またDeepLearningでもC++が散見されます。例えばNvidiaのGPUプログラミングのCUDAは有名だと思います。今回のトピックは個人的なViewで展開している都合上あまり順番は考えておりませんのでご容赦ください。

#C++の基本10個説明
##[1] C++基本（入出力）
C言語では出力はPrintf関数を使いますがC++ではstd::coutを用います。実行速度的にはscanf()の方速いそうですが、ここではstd::coutで進めさせていただきます。入力についてはstd::cinで対応できます。また、>>や<<の矢印は連続して使用することができます。連続して使った場合は空白で区切られて認識されます。

sample.cpp
#include <iostream>

int main(){
    int x,y; //変数を定義する
    std::cin >> x >> y; //標準入力
    std::cout << "和: " << x+y << std::endl; //標準出力
    return 0;
}
出力
200 400
和: 600

加えて競プロでよく使われる配列についての標準入力は次のようになります。ここではarrayではなくvectorを用いています。vectorについてはこのあと述べます。

sample.cpp
#include <iostream>
#include <vector>

int main(){
    int N=3; //サイズを定義する
    std::vector<int> vec(N);
    for(int i=0;i<vec.size();i++){
        std::cin >> vec[i]; //配列に入力した値を格納する
    }
    std::cout << "以下は配列の出力" << std::endl;
    for(int i=0;i<vec.size();i++){
        std::cout << vec.at(i) << std::endl; //配列の中身を標準出力する
    }
    return 0;
}
出力
1 2 3
以下は配列の出力
1
2
3

##[2] 動的配列(ベクトル)
CPPリファレンスによると

  • $vector$はシーケンスコンテナの一種で、各要素は線形に、順序を保ったまま格納される.
  • $vector$コンテナは可変長配列として実装される.
  • 通常の各要素は連続して配置されるため、イテレータだけでなく添え字による要素のランダムアクセスも高速である.

とあります。$vector$は動的配列として使用できるので非常に便利です。Pythonで言うところのappend()が**push_back()で実現出来ます。また配列内検索でfind()**関数を使うこともできます。

sample.cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    //int型の動的配列を定義して初期化する
    std::vector<int> v = {1,99,4};
    //末尾に100を追加する(push_back)
    v.push_back(100);
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    //1番目に500を追加する(insert)
    v.insert(v.begin() + 1, 500);
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    //2番目の要素を削除する(erase)
    v.erase(v.begin()+2);
    for (auto x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    //500があるか配列内を検索する(find)
    int num = 500;
    std::vector<int>::iterator it = std::find(v.begin(), v.end(), num);
    if (it != v.end()) {
        std::cout << num << std::endl;
    }
    else {
        std::cout << "No Exists." << std::endl;
    }
    return 0;
}
出力
1 99 4 100
1 500 99 4 100
1 500 4 100
500

##[3] 再帰関数
再帰関数は関数の中で自分自身を呼び出す関数のことです。この呼び出すことを再帰呼び出しとも言います。再帰関数は$For$文を減らしエレガントなコードにすることも可能です。

fibonacci.cpp
#include <iostream>
#include <vector>

int fib(int n){  //Fibonacci数列の関数を定義する
    if(n==0){
        return 0;
    }else if(n==1){
        return  1;
    }else{
        return fib(n-1)+fib(n-2);
    }
}
int main(){
    for(int i=0; i<20; i++){
        std::cout << fib(i) <<" "; //fibonacci数列を20番目まで出力する
    }
}
出力
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

##[4] Stack(スタック)
Stackはpushとpopの二つの操作が可能なデータ構造を指します。一番上にデータを入れて一番上のデータを取り出せます。

sample.cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    //[10,20,30]を初期値として始める
    std::cout << stack.top() << std::endl; 
    stack.pop(); //[10,20]                            
    std::cout << stack.top() << std::endl;  
    stack.pop(); //[10]
    std::cout << stack.top() << std::endl; 
    stack.pop(); //[]
    return 0;
}
出力
30
20
10

##[5] Queue(キュー）
queueもStackと同じデータ構造です。違いは取り出し方です。一番下のデータをpopで取り出すことが出来ます(First In First Out)。

sample.cpp
#include <iostream>
#include <queue>

int main() {
    std::queue<int> queue;
    queue.push(10);
    queue.push(20);
    queue.push(30);
    
    //[10,20,30]を初期値として始める
    std::cout << queue.front() << std::endl;
    queue.pop(); //[20,30]                            
    std::cout << queue.front() << std::endl;
    queue.pop(); //[30]
    std::cout << queue.front() << std::endl;
    queue.pop(); //[]
    return 0;
}
出力
10
20
30

##[6] 順列
順列(Permutation)もよく出てきます。以下では[1,2,3,4]の4!(通り)の順列を出力しております。next_permutaion()は辞書順で順列を生成するのに利用できます。戻り値はBool型ですがWhile文中で、ある整数列の次の順列が存在するときにtrueを返します。またIotaは整数列を昇順で生成してくれます。第3引数を始点としてシーケンス要素に連続値を代入してくれます。

sample.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main()
{
    int N = 4;
    vector<int> vec(N);
    //Iotaは指定された値から始まる整数列(昇順)を生成し代入する
    iota(vec.begin(), vec.end(), 1); 

    //この時点でvec=[1,2,3,4]
    do {
        for (int i = 0; i <vec.size(); i++) {
            cout << vec[i];
        }
        cout << endl;
    } while (next_permutation(vec.begin(), vec.end()));
    return 0;
}
出力
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

##[7] 最小公倍数
最小公倍数(L.C.M)や最大公約数(G.C.M)の計算は様々な場面に応用できます。LCMとGCM関数を同時に実装して組み合わせて使用することもできますが、今回は最小公倍数を単体で実装しております。

sample.cpp
#include <iostream>

int main(){
	//27と36の最小公倍数を計算する
	int A, B;
	A=36,B=27;
	//一方を整数倍してそれぞれに剰余計算(mod計算)を施す
	for (int i = 1; i < B; i++) {
		int temp = A * i;
		if (temp % B == 0) {
			std::cout << A * i << std::endl; //剰余が0ならそれが最小公倍数に相当する
			break;
		}
	}
	return 0;
}
出力
108

##[8] 範囲For文
C++11で便利になった機能の一つに範囲For文があります。通常のFor文と異なり、配列の各要素を変数に代入してくれます。型推論autoも使えるのでとても便利です。また変数宣言の際にfor(auto &x: vec)として参照変数として使うことも可能です。

sample.cpp
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main()
{
    int N = 10;
    vector<int> vec(N);
    iota(vec.begin(), vec.end(), 1);

    //普通のFor文
    for (int i = 0; i <vec.size(); i++) {
            cout << vec[i] << " ";
    }
    cout << endl;
    
    //範囲For文
    for (auto x : vec) {
        cout << x << " ";
    }
    return 0;
}
出力
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

##[9] 深さ優先
深さ優先(DFS)はかなり有名です。再帰でもStackでも実装できますが、今回は再帰関数を使ってみようと思います。
DFSの参考ページへ
今回のコードは部分和問題の一例をDFSで実装しております。以下説明文です。

整数$a_1,a_2,a_3,...a_n$が与えられている。その中からいくつか選び、その和をちょうど$k$にすることが出来るか。

今回は[9,8,3,1,2]に対して和21を作れるか確かめております。

sample.cpp
#include <iostream>
#include <vector>
using namespace std;

//DFSの再帰関数を定義する
bool dfs(int i, int sum, int k, const vector<int>& a) {
    if (i == a.size()) { return sum == k; }
    else if (dfs(i + 1, sum, k, a)) { return true; }
    else if (dfs(i + 1, sum + a[i], k, a)) { return true; }
    else { return false; }
}

int main() {
    int size = 5;
    int v[] = { 9,8,3,1,2 };
    vector<int> vec(v, end(v));
    int k = 21;
    if (dfs(0, 0, k, vec)) { cout << "Yes" << endl; }
    else { cout << "No" << endl; }
}
出力
Yes

##[10] 幅優先
幅優先(BFS)についてもかなり有名です。
BFS参考ページ

image.png

以下のコードでは上図のノードとエッジの隣接行列を初期化しております。
また

  • 訪問している頂点を表現するキュー(queue)
  • 色の配列(color)
  • ステップ数の配列(dist)

の3つを用意しております。

sample.cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    
    int MAX = 4;
    int start = 0;
    int goal = 3;
    queue<int> queue;
    vector<vector<int>> Matrix{
        {0,1,1,0},
        {0,0,1,0},
        {1,0,0,1},
        {0,0,0,0}
    };

    //色(WHITE=0/ORANGE=1/RED=2)の配列つくる
    vector<int> color(MAX);
    for (int i = 0; i < MAX; i++) {
        color[i] = 0;
    }

    //distの全要素を-1で初期化する
    vector<int> dist(MAX, -1);
    dist[start] = 0;
    queue.push(start);

    //queueが空でなければ継続する
    while (!queue.empty()) {
        int vertex = queue.front();
        queue.pop();
        color[vertex] = 1; //ORANGE
        for (int i = 0; i < MAX; i++) {
            if (Matrix[vertex][i]==1 && color[i]==0) {
                color[i] = 1; //ORANGEにする
                queue.push(i); //visitできるのでqueueに入れる
                dist[i] = dist[vertex] + 1; //start地点からの累積距離を格納する
            }
        }
        color[vertex] = 2; //RED
    }

    //全部visitしていたら全て2が出てくる
    for (int i = 0; i < MAX; i++) {
        cout << color[i]<<" ";
    }
    cout << endl;
    
    //start地点からの累積距離(ステップ数)を表示する
    for (int i = 0; i < MAX; i++) {
        cout << dist[i] << " ";
    }

    return 0;
}
出力
2 2 2 2
0 1 1 2

#まとめ
今回競技プログラミングで用いる基本的なものを備忘録的にまとめてみました。今後問題を解いていく中でメモしていって再度このようにまとめようと思います。実際もっとスマートに書けると思うので思考錯誤していく所存です。次回C++のまとめをする際は1段階レベルを上げたいと思います。

2
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?