LOGICKY BLOG

プログラミングなどに関するブログです

C++ 割ったあまり

参考 「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 - Qiita 分かりやすいmodの説明動画 www.youtube.com www.youtube.com 基本 掛け算、足し算、引き算は、計算途中で余りだす。 引き算は、余りがマイナスになったらmodを足…

C++ 拡張ユークリッドの互除法

ユークリッドの互除法は2つの自然数の最大公約数を求める際に利用します。 a % b == r の場合、a, bの最大公約数は、b, rの最大公約数と等しいです。 b % r == r2、r % r2 == r3と繰り返すことで、最終的に余りが0になったときの割ってる方の数が最大公約数…

C++ 累乗の速いやつ

blog.logicky.com 上記でPythonでやっていますが、C++でもやってみます。どうも速いやつは「繰り返し二乗(自乗)法」という名前らしい。 #define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; using LL = long long; // xのn乗 LL powpow(LL x, LL n) { </bits/stdc++.h>…

C++ 累積和

累積和は、配列の一部の範囲の合計を出すやつです。何回も合計を出す場合に効率化できます。最初に合計を入れる配列を用意して、順番にその位置までの合計を入れていきます。あとはそれを参照するだけで合計出せます。 サンプルコード #define _GLIBCXX_DEBU…

C++ clock

C++

C++で時間計測したいときはclock()が使えます。 参考:clock コードサンプル #include <bits/stdc++.h> #include <unistd.h> using namespace std; int main() { cout << "CLOCKS_PER_SEC: " << CLOCKS_PER_SEC << endl; clock_t start = clock(); cout << "start: " << start << endl</unistd.h></bits/stdc++.h>…

C++ ワーシャルフロイド法

参考:素人によるワーシャルフロイド法 - Qiita グラフ コード #define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; using Graph = vector<vector<int>>; const int INF = 1e9; void warshall_floyd(Graph &G) { int n = G.size(); for (int k = 0; k < n; ++k) { fo</vector<int></bits/stdc++.h>…

C++ ダイクストラ法

blog.logicky.com 上記はPythonでやっていました。C++でやってみます。 参考: 最短経路問題(ダイクストラ法) 対象のグラフ コード #define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; using Graph = vector<vector<int>>; const int INF = 1e9; int n = 8; // 頂点</vector<int></bits/stdc++.h>…

C++ ヒープ (priority_queue)

優先度つきキューは、何をどういう順序で入れても、優先順位の高いものから順に取り出すことができるキューです。内部的にはヒープを使って実装されます。C++では、priority_queueというのがあります。 コード int main() { priority_queue<int> que; que.push(1)</int>…

C++ clang-format

C++

.clang-format というファイルを作って、下記のようにしたら、vscodeで勝手にコンパクトなフォーマットに整形してくれます。私的にはGoogleというのが気に入りました。他の種類はここに説明が書いてあります。 BasedOnStyle: Googl 今のところ、上記で十分で…

C++ 区間DP

参考: 区間DPを勉強してみた - Kutimotiの競プロメモ 区間DPとは何かと言われるといまいちよく分からないが、上記に書いてあることの仕組みは大体分かった。でもまだボトムアップ型のコードしか見てないけど。ナップサック問題と似ていて、細切れにして計算…

C++ 動的計画法(DP)ナップサック問題

典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ - Qiita なんかややこしい。。 全部愚直に一から毎回計算すると大変なやつを、ところどころ覚えておいて表にでもしておけば、計算量減らせるやん的な雰囲気を醸し出しているやつ…

C++ グラフ・探索

参考サイト DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita グラフを隣接リストで表す 隣接リストは、各頂点毎に、隣接する頂点の配列を作ります。 #include <bits/stdc++.h> using namespace std; using Graph = vector<vector<int>>; int mai</vector<int></bits/stdc++.h>…

C++のvector

C++

#include <bits/stdc++.h> using namespace std; int main() { // 1 全部0で初期化 vector<int> v(10, 0); cout << "1: "; for(int x : v) cout << x << ' '; cout << endl; // 2 要素数を設定したらデフォルトでは0で初期化されるっぽい(intの場合) vector<int> v2(10); v2.push_bac</int></int></bits/stdc++.h>…

C++ ビット演算・ビット全探索

ビットは0か1の2通りを表せるやつです。 C++でビット列を作る 下記で作れます。 bitset<8> b("101"); bitset<8> b2(5); 上記は、b, b2共に、00000101 です。引数に文字列を渡すと、そのままビット列として扱います。整数を渡すと、10進数から2進数に変換しま…

VSCodeでC++のコードを自動コンパイル・自動実行する

Code Runnerを使うだけでできます。 Code Runner - Visual Studio Marketplace Code Runnerの出力をターミナルにする settings.json に下記を追加します。 "code-runner.runInTerminal": true, 標準入力を受け付けるコードも問題なく実行できます。