edo1z 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++ ワーシャルフロイド法

参考:素人によるワーシャルフロイド法 - 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++ 区間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++ ビット演算・ビット全探索

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

二分探索

参考:二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita コードはC++です。 int binary_search(int ng, int ok, int key) { while (abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (isOk(mid, key)) ok = mid; else ng = mid; } r…

Python3 - 素因数分解

素因数分解 正の整数 n を素因数分解するための最も単純な方法は、2 から順に √n までの素数で割っていく方法である(Trial division(英語版))。しかし、n が大きくなると、この方法では困難である。 結果 [3, 79, 519507173] 参考:Python Finding Prime…

Python3 - 素数

エラトステネスの篩 エラトステネスの篩 結果 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,…

Python3 - アルゴリズム(重み付きグラフ・最短経路探索・ダイクストラのアルゴリズム)

参考:欲張り法 (greedy strategy) 重み付きグラフ networkxでつくった重みグラフ networkxのコードサンプル 上記は重み付きのグラフです。これはnetworkxで書きました。コードは下記です。 import numpy as np import matplotlib.pyplot as plt import netw…

Python3 - ヒープをnetworkxではなくgraphvizで書いてみる

networkxだときれいに表示できない。posに表示スタイルを設定するようですが、spring_layout、spectral_layout、shell_layoutとかありますが、全部キレイな木を表示してくれる感じじゃない。外部のdotファイルとかいうのを読み込むとできるようですが、graph…

Python3 - ヒープ

ヒープはノードに常に子供が2個あって、子供より親は小さい値を持ちます。ヒープは配列で表せます。配列の0番目は一番上の根ノードです。あとは、k番目のノードの子供は、左が2k+1、右が2k+2番目になります。挿入は最後に挿入して、親ノードと比較して必要に…

Python3 - グラフ・探索

参考:http://www.geocities.jp/m_Hiroi/light/pyalgo05.html グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行…

Python3 - NetworkXでグラフを表示する

https://networkx.github.io/ インストール https://github.com/networkx/networkx/ $ pip install networkx $ pip install decorator Decoratorというのも必要っぽい。両方ともすでに入ってた。 サンプルコード import networkx as nx G=nx.Graph() G.add_n…

Python3 - アルゴリズム(累乗)・計算量

累乗 pow0は遅いやつ。計算量はループをn回回すので、O(n)という。pow1は速いやつ。計算量はO(log n)らしい。 def pow0(x, n): value = 1 for i in range(n): value *= x return value def pow1(x, n): if n == 0: return 1 value = pow1(x, int(n / 2)) val…

ベルマン方程式

ベルマン方程式は、動的計画法(動的な最適化問題)の最適性の必要条件を表す方程式らしい。必要条件は、再帰を使って部分を解くことで全体が解ける状態にあることと、メモ化を使うことです。最適化問題とは、集合内のすべての数値を、ある関数にいれたとき…

Python3 - 動的計画法(フィボナッチ数列)

動的計画法は、分割統治法とメモ化を合わせた方法のことらしい。分割統治法は、問題を細分化して、細かい部分を順に解いていくことで全体を解明するようなことの総称らしい。 分割統治法は、コード的には下記のようになり、再帰することになる。 function co…

greedyアルゴリズム(貪欲法)

greedyアルゴリズムは、全部をN回試して、報酬の平均が最も高いやつを選択するというアルゴリズムです。 当たりか外れがでる機械が4個あって、どれが一番当たり率が高いか分からないのでgreedyアルゴリズムでやってみる想定にします。機械はa~dまであってそ…

codeIQをやってみた

The Essence of Programming 結城 浩さんからのアルゴリズムの問題をやってみました。簡単だと思ったのですが、アルゴリズムとかまだ勉強できてないので合ってるのか分かりません。ミスしてる可能性もあります。一応確認したら出来てる感じでしたが。ただ、…