アルゴリズム


(この文章は巴金督様のhttps://www.youtube.com/watch?v=mBeyFsHqzHg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=4を参照)

りろんぶん


[時間/空間の複雑さ]

  • コンピュータは毎秒3-5億(大まかな推定)
  • を行うことができる.
  • 問題1~5秒かかる
  • 時間の複雑さ
    :入力サイズとトラブルシューティング時間の相関
  • bigoマーキング
    :指定した式を最大値の港湾表現を表す方法
    (時間の複雑さを表す方法)
  • 近似時間複雑度とNの関係(非絶対)
    :1秒を基準に演算の複雑さによって大きく変化し,感覚だけでよい.

  • くうかんふくざつさ
    :入力サイズと問題解決に必要なスペースの相関
    アルゴリズムの問題はあまり気にしなくてもいいです.
    512 MB=1.2億int変数.
  • [整数データ型]

  • short/int/long/long long
    :short型->3万個/int型->21億個(maple fulmesoの大きさです…!)
  • データ型が大きくなったときに使う順番
    int(4 bバイト)->long long(8バイト)->符号なしlong long->string(このように大きい場合がある)
  • [エラーデータ型]


    :float(4 bバイト)とdouble(8バイト)
      doubleと書くのは誤差範囲やいろいろな面でいいので、実数=doubleとしましょう.

    [覚えておきたい3つのこと]


    1)実数の記憶/演算過程では,必然的に誤差が生じる.
    (だから相対誤差の大きいdoubleを必ず使います!!)
        floatの有効数字は6ビット=相対誤差は10^-6までが安全です
        doubleの有効数字は15ビット=相対誤差は10^-15までが安全です
          ex)答えがNの場合2倍ならN-10^-15~N+10^-15まで!
    2)doubleには、長範囲のすべての値を含めることはできません.
       (doubleは有効数字15ビット/longlongは19ビット)
    3)比較エラーの場合は等号は使用できません
    double a = 0.1+0.1+0.1;
    double b = 0.3;
    if(abs(a-b) < 1e-12) cout << "same" ;
    :1 e-12=10^-12の意味!

    機能部(C++)


    [参照者]


    :参照に基づいて演算を行う場合、ポインタを使用しなくてもよい
          : 右側で参照子を使用した演算

    [ STL (Standard Template Library) ]

  • ベクトル
  • ベクトル:可変配列かへんはいれつ
    1)STLを関数パラメータ(値のコピー)とする
    :vectorを関数のパラメータとして使用すると、値がコピーされるため、元の値は変更されません.
    つまり、この場合は「参考者」を使うことができます.
  • 2)STLを関数パラメータに渡す場合(時間的複雑さ)
    :参照者を使用しない場合、ベクトルO(N)をコピーします.
      参照者はアドレスしかスキップできないのでO(1)!

    [標準I/O]

  • Cでは、文字列はchar配列であり、C/C++でStringとして使用される
  • スペースを含む入力を受信した場合
    :getline()、合計

  • scanf/printfおよびcin/cout
    :機能に差はありませんが、cin/coutを使用する際の注意点があります.
    1) ios::sync_with_stdio(0)の作成
    :C++ストリームを使用してCの標準I/Oと同期する
      したがって、I/O量が大きいとタイムアウトする可能性があります.
      対応するコマンドで同期を中断!でもcin/coutしか使えない!
    2)cin.tie(0)の作成
    :cinとcoutのstreamを解く!
      defaultは常にcinの前にcoutのバッファを空にします.
      入力→出力→入力→出力が重複するように並べ替えます.
      でも!これらの不要な接続を切断することで、coteは出力のみを表示するため、パフォーマンスが向上します.
  • ENDはオープンライン+出力バッファクリア機能ですが、パフォーマンスが悪いため、"n"
  • を使用します.

    [珂太は開発とは違う]

  • の開発の鍵はクリーンコードですが、/開発の鍵は私の迅速な作成にあります.
    :グローバル変数でも改行/総合ヘッダーなどを使用!
  • 最後のスペースまたは改行を出力してもよい.
  • デバッガは使用しないでください
    :100行程度しかないので、鼻輪が締め付けられます.
      
  • ヘッダーは
  • 2<bits/stdc++.h>:複数種類のヘッダーの統合-->実際のテープ上でも
  • をブロックする可能性があります.