c++ python 小ネタアルゴリズム対応表

最近atcoderでpythonを使ってTLEをくらうことが多いのでc++への移行を決意しました。そこでよく使いがちな操作の対応表をまとめることにします。(思いつき次第、随時更新します。)

#約数列挙

def divisor_enumetarion(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

vector<long long> divisor_enumetarion(long long n){
    vector<long long> divisors;
    for(long long i=1 ; i*i<=n ; i++){
        if(n%i == 0){
            divisors.push_back(i);
            if(i != n/i){
                divisors.push_back(n/i);
            }
        }
    }
    return divisors;
}

#約数個数列挙

def number_of_divisors(n):
    if n==0:
        return 0
    i=2
    num=1
    while i*i<=n:
        cnt=1
        f=0
        while n%i==0:
            n//=i
            cnt+=1
            f=1
        i+=1
        if f:
            num*=cnt
    if n>1:num*=2
    return num

long long number_of_divisors(long long n){
    if (n==0){
        return 0;
    }else{
        long long i=2;
        long long num=1;
        long long cnt=1;
        long long f=0;
        while (i*i<=n){
            cnt=1;
            f=0;
            while (n%i==0){
                n/=i;
                cnt++;
                f=1;
            }
            i++;
            if (f){
                num*=cnt;
            }
        }
        if (n>1){
            num*=2;
        }
        return num;
    }
}

#素因数分解

def factorize(n):
    i=2
    fct=[]
    while i*i<=n:
        while n%i==0:
            n//=i
            fct.append(i)
        i+=1
    if n>1:         fct.append(n)
    if len(fct)==0: fct.append(1)
    return fct

vector<long long> factorize(long long n){
    long long i=2;
    vector<long long> fct;
    while (i*i<=n){
        while (n%i==0){
            n/=i;
            fct.push_back(i);
        }
        i++;
    }
    if (n>1) fct.push_back(n);
    if (fct.size()==0) fct.push_back(1);
    return fct;
}

#エラトステネスの篩

def ERATOSTHENES(n):
    is_prime=[0,0]+[1]*(n-1)
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2,n+1,i):
                is_prime[j]=0
    return [k for k,v in enumerate(is_prime) if v]

vector<long long>ERATOSTHENES(long long n){
    vector<long long> is_prime(n+1,1);
    is_prime[0]=0;
    is_prime[1]=0;
    long long i=2;
    while(i*i<=n){
        if (is_prime[i]){
            for(long long j=2*i  ;j<n+1  ;j+=i){
                is_prime[j]=0;
            }
        }
        i++;
    }
    vector<long long> primes;
    for(long long i=0  ;i<n+1  ;i++){
        if (is_prime[i]){
            primes.push_back(i);
        }
    }
    return primes;
}

#素数判定

def is_prime(n):
    if n == 1: return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True

bool is_prime(long long n){
    if (n==1) return false;
    long long i=2;
    while (i*i<=n){
        if (n%i==0) return false;
        i++;
    }
    return true;
}

#ある要素のインデックスを求める二分探索

from bisect import*
bisect_left(list,a)
bisect_right(list,a)

lower_bound(vector.begin(),vector.end(),a)-vector.begin()
upper_bound(vector.begin(),vector.end(),a)-vector.begin()

#bit列挙

n=3
for t in range(2**n):
    print([t>>s&1 for s in range(n)])

#out
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]

#二点間の距離

def f(xa,ya,xb,yb):
    return ((xa-xb)**2+(ya-yb)**2)**0.5

#コンビネーション

from math import factorial
def cmb(n,r):
    if n-r<0:
        return 0
    else:
        return factorial(n) // factorial(r) // factorial(n - r)

unsigned long long cmb(long long a,long long b){
    unsigned long long cmb=1;
    long long c=min(b,a-b);
    long long d=2;
    for(long long i=a-c+1  ;i<=a  ;i++){
        cmb*=i;
        while(cmb%d==0 and d<=c){
            cmb/=d;
            d++;
        }
    }
    return cmb;
}

#modコンビネーション

def mod_cmb(n,k,mod):
    def ext_gcd(a,b):
        if b==0:
            return a, 1, 0
        else:
            d,x,y=ext_gcd(b,a%b)
            x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1,n+1):
        p=(p*i)%mod
    for i in range(2,k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q,mod)[1]%mod)%mod)

#最大公約数

from fractions import*
gcd(a,b)

__gcd(a,b) //コンパイラがGCCの時のみ

#ランレングス圧縮

from itertools import*
[len(list(v)) for k,v in groupby(s)]

vector<long long> groupby(string s){
    vector<long long> res;
    long long pre=s[0];
    long long tmp=1;
    for (long long i=1; i<s.size(); i++ ){
        if (s[i]==pre) tmp+=1;
        else{
            res.push_back(tmp);
            pre=s[i];
            tmp=1;
        }
    }
    res.push_back(tmp);
    return res;
}

#累積和

from itertools import*
list(accumulate(numbers))

#もしくは

from numpy import*
cumsum(numbers)

vector<long long> cumsum(vector<long long> numbers){
    for(int i=1  ;i<numbers.size()  ;i++){
        numbers[i]+=numbers[i-1];
    }
    return numbers;
}

#区間和

from numpy import*
def section_sum(numbers,separate):
    sep1=array(numbers[separate:],dtype=int)
    sep2=array(numbers[:-separate],dtype=int)
    sep3=sum(numbers[:separate])
    return insert(sep3+cumsum(sep1-sep2),0,sep3)

vector<long long> section_sum(vector<long long> numbers,long long separate){
    long long n = numbers.size()-separate;
    long long initial_sum;
    decltype(numbers)::iterator nb = numbers.begin();
    decltype(numbers)::iterator ne = numbers.end();
    if (n<=0){
        vector<long long> sep1;
        sep1.push_back(accumulate(nb,ne,0));
        return sep1;
    }else{
        vector<long long> sep1(n),sep2(n),sep3(separate);
        sep1 = vector<long long>(nb+separate , ne);
        sep2 = vector<long long>(nb , ne-separate);
        sep3 = vector<long long>(nb , nb+separate);
        initial_sum=accumulate(sep3.begin(),sep3.end(),0);
        for(long long i=0  ;i<n  ;i++) sep1[i]-=sep2[i];
        for(long long i=1  ;i<n  ;i++) {sep1[i]+=sep1[i-1];sep1[i-1]+=initial_sum;}
        sep1[n-1]+=initial_sum;
        sep1.insert(sep1.begin(),initial_sum);
        return sep1;
    }
}

#コンビネーション

from itertools import*
[*combinations([1,3,6],2)]

#out
[(1, 3), (1, 6), (3, 6)]

#include<bits/stdc++.h>
using namespace std;

void print(vector<vector<long long>> a){for (auto b:a){for (auto c:b){cout<<c<<" ";}cout<<endl;};cout<<endl;}

vector<vector<long long>> combinations(vector<long long> lis,long long repeat){
    long long cnt=0;
    deque<set<long long>> d;
    set<long long> s,tmp;
    d.push_back(s);
    while (cnt<repeat){
        deque<set<long long>> d2;
        for(auto itr=d.begin(); itr!=d.end(); itr++){
            for(auto it=lis.begin()+cnt; it!=lis.begin()+lis.size()+cnt-repeat+1 ; it++){
                tmp=*itr;
                tmp.insert(*it);
                if (tmp.size()==cnt+1){
                    d2.push_back(tmp);
                }
            }
        }
        d=d2;
        cnt++;
    }
    sort(d.begin(), d.end());
    decltype(d)::iterator result = unique(d.begin(), d.end());
    d.erase(result, d.end());
    vector<vector<long long>> ans;
    for(auto item:d){
        vector<long long> ite(item.begin(),item.end());
        ans.push_back(ite);
    }
    return ans;
}

int main(void){
    vector<long long> a={1,3,6};
    vector<vector<long long>> out=combinations(a,2);
    print(out);
}

//out
1 3 
1 6 
3 6 

#パーミュテーション

from itertools import*
[*permutations([1,3,6])]

#out
[(1, 3, 6), (1, 6, 3), (3, 1, 6), (3, 6, 1), (6, 1, 3), (6, 3, 1)]

#include<bits/stdc++.h>
using namespace std;

void print(vector<vector<long long>> a){for (auto b:a){for (auto c:b){cout<<c<<" ";}cout<<endl;};cout<<endl;}

vector<vector<long long>> permutations(vector<long long> lis){
    vector<long long> range,tmp(lis.size(),0);
    vector<vector<long long>> ans;
    
    for(long long i=0  ;i<lis.size()  ;i++){
        range.push_back(i);
    }
    
    do{
        for(long long i=0  ;i<lis.size()  ;i++){
            tmp[range[i]]=lis[i];
        }
        ans.push_back(tmp);
    }while (next_permutation(range.begin(), range.end()));
    return ans;
}

int main(void){
    vector<long long> a={1,3,6};
    vector<vector<long long>> out=permutations(a);
    print(out);
}

//out
1 3 6 
1 6 3 
3 1 6 
6 1 3 
3 6 1 
6 3 1 

#デカルト積

from itertools import*
[*product([1,3,6],repeat=2)]

#out
[(1, 1), (1, 3), (1, 6), (3, 1), (3, 3), (3, 6), (6, 1), (6, 3), (6, 6)]

#include<bits/stdc++.h>
using namespace std;

void print(vector<vector<long long>> a){for (auto b:a){for (auto c:b){cout<<c<<" ";}cout<<endl;};cout<<endl;}

class itertools{
public:

    vector<vector<long long>> ary;
    vector<long long> lis;
    vector<long long> tmp;
    
    void repeating (vector<long long> nums ,vector<long long> lis ,long long repeat){
        if (lis.size()==repeat){
            ary.push_back(lis);
        }else{
            tmp=lis;
            for (auto item:nums){
                tmp.push_back(item);
                repeating(nums,tmp,repeat);
                tmp=lis;
            }
        }
    }
    
    vector<vector<long long>> product(vector<long long> nums,long long repeat){
        repeating(nums,lis,repeat);
        return ary;
    };
};

int main(){
    vector<long long> a={1,3,6};    
    itertools i;
    vector<vector<long long>> out=i.product(a,2);
    print(out);
}

//vector<vector<long long>> out
1 1 
1 3 
1 6 
3 1 
3 3 
3 6 
6 1 
6 3 
6 6 

#上三つをまとめたitertoolsもどき

#include<bits/stdc++.h>

using namespace std;

void print(vector<vector<long long>> a){for (auto b:a){for (auto c:b){cout<<c<<" ";}cout<<endl;};cout<<endl;}

class itertools{
public:
    //----------------------------combinations---------------------------    
    vector<vector<long long>> combinations(vector<long long> lis,long long repeat){
        long long cnt=0;
        deque<set<long long>> d;
        set<long long> s,tmp;
        d.push_back(s);
        while (cnt<repeat){
            deque<set<long long>> d2;
            for(auto itr=d.begin(); itr!=d.end(); itr++){
                for(auto it=lis.begin()+cnt; it!=lis.begin()+lis.size()+cnt-repeat+1 ; it++){
                    tmp=*itr;
                    tmp.insert(*it);
                    if (tmp.size()==cnt+1){
                        d2.push_back(tmp);
                    }
                }
            }
            d=d2;
            cnt++;
        }
        sort(d.begin(), d.end());
        decltype(d)::iterator result = unique(d.begin(), d.end());
        d.erase(result, d.end());
        vector<vector<long long>> ans;
        for(auto item:d){
            vector<long long> ite(item.begin(),item.end());
            ans.push_back(ite);
        }
        return ans;
    }
    //----------------------------combinations---------------------------
    
    //----------------------------permutations---------------------------
    vector<vector<long long>> permutations(vector<long long> lis){
        vector<long long> range,tmp(lis.size(),0);
        vector<vector<long long>> ans;
        
        for(long long i=0  ;i<lis.size()  ;i++){
            range.push_back(i);
        }
        
        do{
            for(long long i=0  ;i<lis.size()  ;i++){
                tmp[range[i]]=lis[i];
            }
            ans.push_back(tmp);
        }while (next_permutation(range.begin(), range.end()));
        return ans;
    }
    //----------------------------permutations---------------------------
    
    //------------------------------product------------------------------
    vector<vector<long long>> ary;
    vector<long long> lis;
    vector<long long> tmp;

    void repeating (vector<long long> nums ,vector<long long> lis ,long long repeat){
        if (lis.size()==repeat){
            ary.push_back(lis);
        }else{
            tmp=lis;
            for (auto item:nums){
                tmp.push_back(item);
                repeating(nums,tmp,repeat);
                tmp=lis;
            }
        }
    }

    vector<vector<long long>> product(vector<long long> nums,long long repeat){
        repeating(nums,lis,repeat);
        return ary;
    //------------------------------product------------------------------
    
    
    
    };
};

int main(){
    itertools i;
    vector<vector<long long>> out=i.product(vector<long long> {0,1,2},2);
    vector<vector<long long>> out2=i.combinations(vector<long long> {0,1,2},2);
    vector<vector<long long>> out3=i.permutations(vector<long long> {0,1,2});
    print(out);
    print(out2);
    print(out3);
}

//out
0 0 
0 1 
0 2 
1 0 
1 1 
1 2 
2 0 
2 1 
2 2 

0 1 
0 2 
1 2 

0 1 2 
0 2 1 
1 0 2 
2 0 1 
1 2 0 
2 1 0

#median(偶数の時は0 indexed n//2-1の値)を二本のpriority_queueで高速に求める

from heapq import*

class median_tree(object):
    def __init__(self):
        self.lower_than_med=[]
        self.higher_than_med=[]
        self.count=0
        self.low=0
        self.high=0
        self.median=0
    def push(self,x):
        self.count=1-self.count
        if self.count:
            y=heappushpop(self.higher_than_med,x)
            heappush(self.lower_than_med,-y)
            self.low +=-y
            self.high+=x-y
        else:
            y=heappushpop(self.lower_than_med,-x)
            heappush(self.higher_than_med,-y)
            self.low -=x+y
            self.high-=y
        self.median=-self.lower_than_med[0]

how to use → https://atcoder.jp/contests/abc127/submissions/5716256

class median_tree{
public:
    priority_queue<long long>lower_than_med,higher_than_med;
    long long count=0;
    long long low=0;
    long long high=0;
    long long median=0;
    long long y;
    
    long long push(long long x){
        count=1-count;
        if (count){
            higher_than_med.push(-x);
            y=higher_than_med.top();
            higher_than_med.pop();
            lower_than_med.push(-y);
            low+=y;
            high+=x+y;
        }
        else{
            lower_than_med.push(x);
            y=lower_than_med.top();
            lower_than_med.pop();
            higher_than_med.push(-y);
            low-=x-y;
            high+=y;
        }
        median=lower_than_med.top();
        return 0;
    }
};

how to use → https://atcoder.jp/contests/abc127/submissions/5719885

#最長部分文字列

from heapq import*

def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:heappush(dp,chr_idx)
            print(dp)
    return len(dp)

#おまけ(python高速化黒魔術など)

import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意
sys.setrecursionlimit(10**6)   #再帰深度制限回避

import functools
@functools.lru_cache(maxsize=None)   
#関数かクラスを勝手にもメモ化してくれる 場合によって遅くなったりもするので注意