競プロでつかうC++の基礎 ＋ アルゴリズム

Pythonばっかりやってると競プロで必須なC++基本知識をたまに忘れるのでまとめておく

• if文
  ifの内容が1行なら中括弧{}はいらない

      if(a<b) cout << b << endl;
  

• 条件分岐
  Pythonでは「and」や「or」で論理演算を表現していますが、Cでは「&&」でand・「||」でorを表現できる

      if( 1 <= a && a <= 9) cout << a << endl;
  

  ビット演算であれば & , | １つでandとorの演算ができる。(ちなみに排他的論理和は ^ )

• 文字列の比較
  複数あっても辞書順に大小が比較できる。

      string a="abc" , b="xyz";
      if( a<b ) cout << b << endl;
      else cout << a << endl;
  
      /// output : xyz
  

• 長い整数
  long long。

• 浮動小数点の桁数指定出力
  iomanip をインクルードして指定する。

      include<iostream>
      include<iomanip>
  
      int main(){
          double pi = 3.1415926535...;
          std::cout << fixed << setprecision(5) << pi << endl;
          /// 5桁分(小数点第4位まで)出力される
          /// output : 3.1415
          
          return 0;
  

• 配列
  要素を最初から指定するときには、中括弧{}で記述する。また多次元配列を定義するときには要素の数を最初に指定する必要がある。

      int ary[10] = {0}
      /// aryの要素 : [0,0,0,0,0,0,0,0,0,0]
  
      int square[3][3] = {
          {0,0,0},
          {0,0,0},
          {0,0,0}
      };
      /// (要素をあらかじめ入れる必要はない)
  

• EOFまでの入力
  文字入力の指定がないとき(複数行にわたっての入力、終了条件がないとき)

      char ch;
      while(cin >> ch){
          // 処理        
      }
  

• string
  stringクラスに含まれるメソッド
  size() : サイズを返す
  insert()/erase() : 指定した場所の文字の挿入・削除
  find() : 文字列を探す
  substr() : 指定した部分文字列を返す
  replace() : 指定した部分文字列を新しいのに置換する

• cmath
  数学関連の関数

• 関数とstruct
  関数は戻り値の型を指定する必要がある。戻り値がないならvoid

      #include<iostream>
      #include<string>
      
      void print(std::string s){
          std::cout << s << std::endl;
      }
      
      int main(void){
          print("abc");
      }
  
      /// output : abc
  

structでは、複数の型をまとめた新しい型を作ることができる。

        #include<iostream>
        #include<string>
        using namespace std;

        struct Test {
            int x;
            string s;
        }
        int main(){
            Test t;
            t = {10,"aaa"};
            cout << t.x << " " << t.s << endl;
        }

        /// output : 10 aaa

この中に関数も定義できる

        struct Test{
            int x;
            string s;
            int add(){
                if(s=="abc") return x + 1;
                else return x;
            }
        }
        int main(void){
            Test t;
            t = { 10,"aaa" };
            cout << t.add() << endl;
        }

        /// output : 10

アルゴリズム

挿入ソート

前方の要素をソート済として、後部の要素をソート済の部分に挿入するアルゴリズム。
ある程度昇順に並んでいるデータであれば有効だが、その逆ではO(N^2)の計算量。。。

test.c

// 関数として記述：整列する配列の個数のみ引数に渡す

void insertion_sort(int n){
    int a[n+1]; //最後の要素は入れ替え用
    for(int i=0;i<n;i++){
        std::cin >> a[i]; // 入力
    }

    for(int i=0;i<n;i++){
        // iの位置を軸にして移動
        for(int j=0;j<=i;i++){
            if(a[i-j-1] > a[i-j]){
                a[n] = a[i-j-1];   // 退避
                a[i-j-1] = a[i-j]; // 入れ替え
                a[i-j] = a[n];
            }
        }
    }
    // 以上
}

最大公約数を求める

高校数学Aで出る「ユーグリッドの互除法」をつかう。

a \geqq b　のとき、a,bの最大公約数はb,r(aをbで割った余り)の最大公約数と等しい

これを繰り返すことで、膨大な数でも r=0 のとき bが最大公約数となる。

test.c

// 二つの引数の最大公約数を返す関数
int gcd(int a,int b){
    int t; // 退避用変数
    while(b!=0){
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}

素数判定

nが素数かどうかを調べるのは、シンプルに1からnまでのうち1とn以外に割り切れる数がないかforでまわせばいい。
...ただ、nが1234567897とか10の10乗とかになるともし素数なら(10の10乗)回の計算量が必要になる。競プロでは計算量は命なのでどうにかしないといけない。

素数をある程度まとめてそれで割れるかを調べるのも手だが、膨大な数には手を出せなくなる。
そこで、判定する数nの平方根までを範囲にして検索すると半減できる。
（16は4の2乗、25は5の2乗で、17から24までの数は5と5より大きい数であることはないので）

test.c

#include<cmath>

// 素数判定プログラム
bool isPrimeNumber(int n){
    bool p = true;
    for(int i=2;i<=sqrt(n);i++){
        // nがiで割り切れる => 因数を持つ => 素数でない(合成数) 
        if( n % i == 0 ){
            p = false;
            return p;
        }
    }
    return p;
}

~忘れそうだったらさらに更新予定~