# 競プロで使えそうなライブラリ・手法(初心者向け)
このライブラリでは
`using ll = long long;`を使用しています．
必ずはじめにこれを記載するようにしてください．
## 二項係数(コンビネーション,nCr)
$nCr$の計算を$O(r)$で行える
オーバーフローに注意(__int128_tを使うとマシになるかも)
```cpp=
ll comb(ll n, ll r) {
ll res = 1;
if (n / 2 < r) {
r = n - r;
}
for (ll i = 1; i <= r; i++) {
res *= (n - i + 1);
res /= i;
}
return res;
}
```
## パーミュテーション(nPr)
$nPr$の計算を$O(r)$で行える
```cpp=
ll perm(ll n, ll r){
if(r<=0) return 1;
else return n*perm(n-1,r-1);
}
```
## bit全探索
いくつかの要素を自由に選んで条件を満たすかという問題で使える，配列内の要素の選び方をすべて試す探索法
計算量に$O(2^N)$が掛かる
```cpp=
ll N;
for(int bits=0;bits<(1LL<<N);bits++){
for(int i=0;i<N;i++){
if((1<<i)&bits){ //i番目の要素を選ぶ
}
}
}
```
## 二分探索
条件を満たす境界を高速に探し出すアルゴリズム
計算量に$O(\log(N))$が掛かる
```cpp=
int ok=0,ng=N,mid;// 条件を満たすインデックスをok,条件を満たさないインデックスをngに代入
while(abs(ok-ng)>1){
mid=(ok+ng)/2;
if(/*調べたい条件*/) ok=mid;//条件を満たしているとき
else ng=mid;//条件を満たしていないとき
}
cout<<ok<<endl;//okが答え
```
使用例(配列Aの中でK以下の最大の数を高速に探し出すプログラム)
```cpp=
int main(){
int N,K;
cin>>N>>K;
vector<ll> A(N);
rep(i,N) cin>>A[i];
int ok=0,ng=N,mid;// 条件を満たすインデックスをok,条件を満たさないインデックスをngに代入
while(abs(ok-ng)>1){
mid=(ok+ng)/2;
if(A[mid]<=K) ok=mid;//条件を満たしているとき(AがK以下)
else ng=mid;//条件を満たしていないとき
}
cout<<A[ok]<<endl;
}
```
## 尺取り法
範囲をずらしながら条件を満たす連続区間を数えるアルゴリズム
以下のコードではAの中で総和がvalueになる連続区間を数えている
計算量は$O(N)$
```cpp=
int main() {
int l = 0, r = 0, value = 10, now = 0;
vector<int> A = {1, 3, 6, 1, 4, 8, 3, 2};
vector<pair<int, int>> ans;
while(true){
if(r >= A.size()) break;
now += A[r];
r++;
while(now > value){
now -= A[l];
l++;
}
if(now == value){
ans.push_back(make_pair(l, r));
}
}
}
```
## BFS(グリッドグラフ)
グリッドグラフで使える幅優先探索
グリッドグラフは
```
.S##
#..#
..#.
#..G
```
のようなグラフ
```cpp=
ll H,W;
vector<string> G;//グリッドグラフ
vector<ll> dx={0,1,0,-1},dy={1,0,-1,0};
//探索済み(正確にはqueueにpush済み)かの情報
vector<vector<bool>> seen(H,vector<bool>(W,false));
pair<ll,ll> start,goal;
queue<pair<ll,ll>> q;
q.push(start);
seen[start.first][start.second]=true;
while(!q.empty()){
auto [y,x]=q.front();
q.pop();
// 各マスで行いたい処理
for(ll i=0;i<4;i++){
ll nexty=y+dy[i],nextx=x+dx[i];
if(0<=nexty&&nexty<H&&0<=nextx&&nextx<W){
if(!seen[nexty][nextx]){
if(/*マスに進む条件*/G[nexty][nextx]!='#'){
seen[nexty][nextx]=true;
q.push({nexty,nextx});
}
}
}
}
}
```
## ランレングス圧縮
文字列Sを，文字+何個その文字が連続するかという情報にするアルゴリズム
計算量は$O(N)$
例
aaabbabcc→a3b2a1b1c2
```cpp=
vector<pair<int, char>> RunLength(string S)
{
int N = S.size();
vector<pair<int, char>> memo;
if (N == 1)
{
memo.push_back(make_pair(1, S.at(0)));
return memo;
}
int tempo = 1;
for (int i = 1; i < N; i++)
{
if (i != N - 1)
{
if (S.at(i) == S.at(i - 1))
tempo++;
else
{
memo.push_back(make_pair(tempo, S.at(i - 1)));
tempo = 1;
}
}
else
{
if (S.at(i) == S.at(i - 1))
{
tempo++;
memo.push_back(make_pair(tempo, S.at(i - 1)));
}
else
{
memo.push_back(make_pair(tempo, S.at(i - 1)));
memo.push_back(make_pair(1, S.at(i)));
}
}
}
return memo;
}
```
## エラトステネスの篩
素数かどうかの情報が格納された配列を$O(\log\log N)$で返すアルゴリズム
```cpp=
vector<bool> Eratosthenes(int N){
vector<bool> ans(N+1,true);
ans[0]=false;
ans[1]=false;
for(int i=2;i*i<=N;i++){
if(ans[i]){
for(int j=i*i;j<=N;j+=i){
ans[j]=false;
}
}
}
return ans;
}
```
## 素因数分解
素因数分解を行うアルゴリズム
高速素因数分解とは違い，非常に大きい値でも行える．
計算量は$O(\sqrt{N})$
```cpp=
//キーに素因数，値に何乗かを格納した連想配列を返すタイプ
template<class T>
map<T,T>prime_factorization(T N){
map<T,T> ans;
T X=N;
for(T i=2;i*i<=N;i++){
if(X%i!=0)continue;
if(X==1)break;
while(X%i==0){
ans[i]++;
X/=i;
}
}
if(X!=1)ans[X]++;
return ans;
}
//素因数を配列に詰めたタイプ
template<class T>
vector<T>prime_factorization2(T N){
vector<T> ans;
T X=N;
for(T i=2;i*i<=N;i++){
if(X%i!=0)continue;
if(X==1)break;
while(X%i==0){
ans.push_back(i);
X/=i;
}
}
if(X!=1)ans.push_back(X);
return ans;
}
```
## 高速素因数分解
素因数分解を高速で行えるアルゴリズム
前計算で各値の最小の素因数を求めるため，非常に大きい値を素因数分解しようとするとメモリがとんでもないことになる
計算量は前計算が$O(N\log N)$，高速素因数分解が$O(\log N)$
```cpp=
//最初にSPFを実行
vector<int> SPF(int N){
vector<int> ans(N+1);
for(int i=0;i<=N;i++){
ans[i]=i;
}
for(int i=2;i*i<=N;i++){
if(ans[i]==i){
for(int j=i*i;j<=N;j+=i){
ans[j]=i;
}
}
}
return ans;
}
map<int,int> FPF(int X,vector<int> &spf){
map<int,int> ans;
while(X!=1){
ans[spf[X]]++;
X/=spf[X];
}
return ans;
}
//使用例
int main(){
auto spf=SPF(200000);//入力の最大値まででSPF配列を作成
int N;
cin>>N;
auto ans=FPF(N,spf);
auto itr=ans.begin();
for(int i=0;i<ans.size();i++,itr++){
cout<<(*itr).first<<"^"<<(*itr).second<<endl;
}
return 0;
}
```
## 繰り返し二乗法
$A^N$を$O(\log N)$で求められるアルゴリズム
実数の累乗だとstd::powlでいいが，行列累乗や多項式の累乗をするときに本領を発揮する
```cpp=
ll Pow(ll X, ll N)
{
ll ans = 1;
while (N)
{
if (N & 1)
{
ans *= X;
}
X *= X;
N >>= 1;
}
return ans;
}
```
## 1次元累積和
ある範囲の総和を高速に求められるデータ構造
```cpp=
// 累積和
// [l,r)の範囲の総和をO(1)で求められる
// 前計算O(N),クエリの処理O(1)
class cumulative_sum {
private:
vector<long long> v;
int N;
public:
cumulative_sum(int n) {
v.resize(n + 1);
for(auto &x : v)
x = 0;
N = n;
}
cumulative_sum(vector<long long> &A) {
v.resize(A.size() + 1);
v[0] = 0;
N = A.size();
for(int i = 0; i < A.size(); i++)
v[i + 1] = A[i];
}
// v[idx]にxを代入
// O(1)
void set(long long idx, long long x) {
if(idx > 0 && idx <= N)
v[idx + 1] = x;
}
// 累積和を構築
// O(N)
void build() {
v[0] = 0;
for(int i = 1; i <= N; i++)
v[i] += v[i - 1];
}
// [l,r)の総和を返す
// O(1)
long long prod(int l, int r) { return v[r] - v[l]; }
};
```
使用例
```cpp=
int main(){
ll N,x;
cin>>N;
cumlative_sum C(N);// 長さNの累積和を宣言
rep(i,N){
cin>>x;
C.set(i,x);// C[i]にxを代入
}
C.build();// 累積和を構築
cout<<C.prod(0,N)<<endl;//インデックスが0以上N未満の要素の総和を出力
cout<<C.prod(2,5)<<endl;//インデックスが2以上5未満の要素の総和を出力
vector<ll> A(N);
rep(i,N) cin>>>A[i];
cumlative_sum D(A);//配列Aをもとに累積和を宣言することも可
D.build();
cout<<D.prod(0,N)<<endl;
return 0;
}
```
Sign in with Wallet
Connect another wallet