LoginSignup
14
16

More than 3 years have passed since last update.

@KyleKatarn

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

Last updated at Posted at 2019-05-18

最近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)   
#関数かクラスを勝手にもメモ化してくれる 場合によって遅くなったりもするので注意
14
16
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
16