2021-10-21

ソートされたリストの二分探索

長さ $N$ の数列に対して、以下のことを行える。

$O(N\log N)$ 　前処理　昇順ソートする

$O(\log N)$ $x$ 以上の/以下の/より大きい/より小さい要素の個数
$O(\log N)$ $x$ 以上の/より大きい要素のうち最小のindex
$O(\log N)$ $x$ 以下の/より小さい要素のうち最大のindex

l.sort()

from bisect import bisect_left,bisect_right

count_x_or_more_than_x=len(l)-bisect_left(l,x)      # x以上の要素の個数
count_more_than_x=len(l)-bisect_right(l,x)          # xより大きい要素の個数
count_x_or_less_than_x=bisect_right(l,x)            # x以下の要素の個数
count_less_than_x=bisect_left(l,x)                  # xより小さい要素の個数

# if index=len(l): 存在しない
index_x_or_more_than_x=bisect_left(l,x)             # x以上の要素のうち最小のindex
index_more_than_x=bisect_right(l,x)                 # xより大きい要素のうち最小のindex

# if index=-1: 存在しない
index_x_or_less_than_x=bisect_right(l,x)-1          # x以下の要素のうち最大のindex
index_less_than_x=bisect_left(l,x)-1                # x未満の要素のうち最大のindex

例題

参考

2021-10-18

トポロジカルソートと閉路検出

トポロジカルソート
有向グラフの閉路の検出とトポロジカルソート

閉路あり→ -1
閉路なし→ list（任意の有向辺 $e_{u \rightarrow v}$ に対し $\mathrm{index}(u) < \mathrm{index}(v)$ ）

計算量
$O(N+M)$ 　( $N$ :頂点数, $M$ :辺の数)

def topo_sort(g,n):
    order=[]
    indeg=[0]*n
    for v in range(n):
        for v1 in g[v]:
            indeg[v1]+=1
    st=[v for v in range(n) if indeg[v]==0]
    while st:
        v=st.pop()
        order.append(v)
        for v1 in g[v]:
            indeg[v1]-=1
            if indeg[v1]==0:
                st.append(v1)
    if len(order)==n:
        return order
    return -1                       #閉路あり

(stackはqueueでもheapqでもなんでも良い)

使い方

#  ↑→→↓
#  0  1 
#  ↓→→↑ の時
n=2
g=[[1],[0]]
print(topo_sort(g,n))

#  0→1→2
#    ↓ ↑
#    3→4
n=5
g=[[1],[2,3],[],[4],[2]]
print(topo_sort(g,n))

例題
ABC223D
ABC139E

参考
木上のトポロジカルソートのコード、強連結成分分解のコードを近日中載せます。

2021-10-16

桁DPのフォーマット

桁DP

$N$ 以下の数のうち条件を満たすものを答えよというような問題で使える。

計算量
$O(Bk\log N)$ 　（ $k$ ：状態数、 $B$ ：桁に置ける数字の種類）

ソースコード
$N$ 以下に必ずなるかを表す添字 $less$ が肝となるが、遷移を書くのによく手間取る。 $less$ のことを考えなくても書けるソースコードを示す。
(!!!書き換えるとしたところを問題によって変える。)

l=[ord(i)-ord('0') for i in str(n)]
dig=len(l)
dp=[[[0,0] for _ in range(kmax)] for _ in range(dig+1)]     #kmax   !!!書き換える
dp[0][0][0]=1                                               #初期条件!!!書き換える
for i in range(dig):
    for less in range(2):
        for j in range(10):
            if less==0 and j>l[i]:
                break
            for k in range(kmax):                           #kmax   !!!書き換える
                #配るDP i+1桁目にjを置く k→k1に変化
                dp[i+1][k1][less|(j<l[i])]+=dp[i][k][less]  #遷移 !!!書き換える

例
TDPC-E
求めるもの
（N以下の正整数のうち各位の和がDの倍数であるものの個数）%1,000,000,007
$dp_{i,k,less}=$ （i桁目まで決めた時dで割ったあまりがkの個数、less:N以下必ずなるか）

d=int(input())
n=int(input())
l=[ord(i)-ord('0') for i in str(n)]
dig=len(l)
dp=[[[0,0] for _ in range(d)] for _ in range(dig+1)]        #kmax   !!!書き換える
dp[0][0][0]=1                                               #初期条件!!!書き換える
mod=10**9+7
for i in range(dig):
    for less in range(2):
        for j in range(10):
            if less==0 and j>l[i]:
                break
            for k in range(d):                              #kmax   !!!書き換える
                #配るDP i+1桁目にjを置く 各位の和をdで割ったあまりはk→(k+j)%dに変化
                dp[i+1][(k+j)%d][less|(j<l[i])]+=dp[i][k][less]  #遷移 !!!書き換える
                dp[i+1][(k+j)%d][less|(j<l[i])]%=mod

ans=sum(dp[-1][0])-1
ans%=mod
# dp[-1][0][0]:Nが条件を満たすか
# dp[-1][0][1]:N未満の数のうち条件を満たしている個数
# 1:N=0の場合は含まれないので引く

print(ans)

例題
TDPC-E
ABC029D
ABC117D
ARC127A 状態をもう一つ作り4次元で桁DPを行う

参考

2021-10-15

エラトステネスの篩による素数判定・素因数分解・約数列挙

エラトステネスの篩

$N$ 以下の数に対して、以下のことができる。

$O(N\log\log N)$ 　前処理

$O(1)$ 　　　　　　素数判定
$O(\log N)$ 　　　　素因数分解
$O(\log N)$ 　　　　約数の個数　 $d(N)$
$O(\log N)$ 　　　　約数の総和　 $\sigma (N)$
$O(d(N))$ 　　　　　約数列挙

ソースコード

_n=10**5        #最大値
sieve=list(range(_n+1))
sieve[0]=sieve[1]=-1
for i in range(2,int(_n**0.5)+1):
    if sieve[i]==i:
        for j in range(i*i,_n+1,i):
            if sieve[j]==j:
                sieve[j]=i

def isprime(x):
    return sieve[x]==x

def factorization(x):   #O(logN)
    ans=[] 
    while x>1:
        p=sieve[x]
        ans.append([p,0])
        while sieve[x]==p:
            x//=p
            ans[-1][-1]+=1
    return ans

def d(x):              #O(logN) 約数の個数
    ans=1
    while x>1:
        p=sieve[x]
        cnt=0
        while sieve[x]==p:
            x//=p
            cnt+=1
        ans*=cnt+1
    return ans

def sigma(x):          #O(logN) 約数の総和
    ans=1
    while x>1:
        p=sieve[x]
        cnt=0
        res=1
        while sieve[x]==p:
            res*=p
            cnt+=res
            x//=p
        ans*=cnt+1
    return ans

def divisors(x):    #O(d(x)) 約数の列挙
    ans=[1]
    while x>1:
        p=sieve[x]
        t=len(ans)
        while sieve[x]==p:
            for i in ans[-t:]:
                ans.append(i*p)
            x//=p
    #ans.sort()
    return ans

使い方

#素数判定
print(isprime(1))           #   >>False
print(isprime(2))           #   >>True

#素因数分解
print(factorization(12))    #   >> [[2, 2], [3, 1]]
print(factorization(1024))  #   >> [[2, 10]]

#約数の個数
print(d(18))                #   >> 6
print(d(169))               #   >> 3

#約数の総和
print(sigma(18))            #   >> 39
print(sigma(169))           #   >> 183

#約数の列挙
print(divisors(18))         #   >> [1, 2, 3, 6, 9, 18]
print(divisors(169))        #   >> [1, 13, 169]

例題
ABC117E

参考

2021-10-14

二次元IMOS法

累積和

二次元IMOS法

$H×W$ の二次元配列 $A$ に対して、以下のことができる。

$O(1)$ 　　区間作用(構築前のみ)　 $A_{ij}+=x ~~(i_1 \leq i \leq i_2,j_1 \leq j \leq j_2)$
$O(HW)$ 　構築
$O(1)$ 　　一点取得(構築後のみ)　 $A_{ij}$

ソースコード

class IMOS2:
    def __init__(self,h,w):
        self.h,self.w=h+1,w+1
        self.l=[0]*(self.h*self.w)
    def add(self,i,j,i_,j_,x):      #矩形[(i,j),(i_,j_))に+xを区間作用
        self.l[i*self.w+j]+=x
        self.l[i_*self.w+j_]+=x
        self.l[i*self.w+j_]-=x
        self.l[i_*self.w+j]-=x
    def build(self):                #構築
        for j in range(self.w):
            for i in range(1,self.h):
                self.l[i*self.w+j]+=self.l[(i-1)*self.w+j]
        for i in range(self.h):
            for j in range(1,self.w):
                self.l[i*self.w+j]+=self.l[i*self.w+j-1]
    def get(self,i,j):              #一点取得
        return self.l[i*self.w+j]
    def __str__(self):
        return '\n'.join([str(self.l[i*self.w:(i+1)*self.w]) for i in range(self.h)])


imos=IMOS2(2,2)
print(imos)         #   [0, 0, 0]
                    #   [0, 0, 0]
                    #   [0, 0, 0]

imos.add(0,0,2,2,1)
print(imos)         #   [1, 0, -1]
                    #   [0, 0, 0]
                    #   [-1, 0, 1]

imos.add(0,1,2,2,10)
print(imos)         #   [1, 10, -11]
                    #   [0, 0, 0]
                    #   [-1, -10, 11]

imos.build()
print(imos)         #   [1, 11, 0]
                    #   [1, 11, 0]
                    #   [0, 0, 0]

print(imos.get(0,0))#   1
print(imos.get(1,1))#   11

例題
競プロ典型90問-028

参考
一次元のIMOS法
k-penciler.hatenablog.com

2021-10-13

IMOS法

累積和

IMOS法

長さ $N$ の数列 $A$ に対して、以下のことができる。

$O(1)$ 　　区間作用(構築前のみ)　 $A_k+=x ~~(i \leq k \leq j)$
$O(HW)$ 　構築
$O(1)$ 　　一点取得(構築後のみ)　 $A_i$

ソースコード

class IMOS:
    def __init__(self,n):
        self.n=n+1
        self.l=[0]*self.n
    def add(self,i,j,x):      #区間[i,j)に+xを区間作用
        self.l[i]+=x
        self.l[j]-=x
    def build(self):                #構築
        for i in range(self.n-1):
            self.l[i+1]+=self.l[i]
    def get(self,i):              #一点取得
        return self.l[i]
    def __str__(self):
        return str(self.l)


#使い方

imos=IMOS(5)  #長さ5の数列
print(imos)         #   [0, 0, 0, 0, 0, 0]

imos.add(0,3,10)    #   [ ↓, ↓, ↓,    ,  ,  ]
print(imos)         #   [10, 0, 0, -10, 0, 0]

imos.add(2,5,1)     #   [  ,  , ↓,   ↓, ↓,   ]
print(imos)         #   [10, 0, 1, -10, 0, -1]

imos.add(1,4,100)   #   [  ,   ↓, ↓,   ↓,     ,   ]
print(imos)         #   [10, 100, 1, -10, -100, -1]

imos.build()
print(imos)         #   [10, 110, 111, 101, 1, 0]

print(imos.get(3))  #   1
print(imos.get(2))  #   11

例題
ABC035C

参考
二次元のIMOS法
k-penciler.hatenablog.com

2021-10-12

二次元累積和の一般化

累積和

二次元累積和(群の区間取得)

$H×W$ の二次元配列 $A$ 、集合 $G$ 二項演算子 $*$ ( $(G,*)$ は群)に対して、以下のことができる。

$O(HW)$ 　前処理
$O(1)$ 　　区間取得

　　　　　　　 $(A_{ij}*\dots*A_{ij'})*\dots*(A_{i'j}*\dots*A_{i'j'})~~(i\leq i',j\leq j')$

群は結合律・単位律・逆元律を満たす。

ソースコード(二項演算子が加算の場合)

class Acc2:
    def __init__(self,l,f,unit,inv):
        self.h,self.w=len(l),len(l[0])
        self.acc2=[[unit]*(self.w+1) for _ in range(self.h+1)]
        self.f,self.inv=f,inv
        for i in range(self.h):
            for j in range(self.w):
                self.acc2[i+1][j+1]=f(f(f(self.acc2[i][j+1],self.acc2[i+1][j]),inv(self.acc2[i][j])),l[i][j])
    def sum(self,i,j,i_,j_):
        return self.f(self.f(self.f(self.acc2[i_][j_],self.inv(self.acc2[i][j_])),self.inv(self.acc2[i_][j])),self.acc2[i][j])
    def get(self,i,j):
        return self.sum(i,j,i+1,j+1)
    def __str__(self):
        return '\n'.join([str(i) for i in self.acc2])

###### Settings ######
_f=lambda x,y: x+y
_unit=0
_inv=lambda x: -x
######################


l=[
    [1000,   1,  10, 100],
    [ 100,  10,   3,1000]
]

acc=Acc2(l,_f,_unit,_inv)

# 使い方
print(acc.sum(0,0,2,2))     #[ooxx]
                            #[ooxx] の合計      >>1111
                        
print(acc.sum(1,0,2,3))     #[xxxx]
                            #[ooox] の合計      >>113

print(acc.get(0,0))         #l[0][0]           >>1000

加算以外の場合
####で囲まれた部分を変更すると使える。

加算+mod

###### Settings ######
mod=10**9+7
_f=lambda x,y:(x+y)%mod #二項演算子
_unit=0                 #単位元
_inv=lambda x:(-x)%mod  #逆元
######################

例題
ARC025B
ABC130E
ABC203D
典型90問-081

参考記事
一次元の累積和についてはこちら
k-penciler.hatenablog.com