2023-05-04

Z algorithm, KMP法(MP法), BM法を実装した

2023/05/04初版公開
atcoderやってます。緑です。python使ってます。

アルゴリズムの紹介・解説は書きません。これから実装しようとしている人向けに感想・役に立つかもしれない情報を記します。

まず、これらのアルゴリズムを実装するのは大変でした。解説をみればやってることはなんとなくわかりますが、実装するとなると難易度が上がりました。 seg木を実装した時の5倍の時間 × 3(種類のアルゴリズム) がかかりました。初歩的なアルゴリズムなのに実装できない!ってなってる人はこの記事を見て安心してください。

実装したアルゴリズムが正しく動くかどうかは AOJ-ALDS-14-Bで確認できます。
(BM法は最悪計算量を改善しない限りTLEになる可能性大)
またZ-algorithmはLibrary-checkerでも確認できます。

これから実装する人には、以下の手順をお勧めします。
①各アルゴリズムのいろいろなバリエーションをなんとなく理解する。
②自分が(最終的に)どのバリエーションを実装するのか決める
③はじめは一番簡単そうな種類を実装し、ちゃんと動作することを確認して次に簡単そうなverを実装する

①について、以下のキーワードがなんとなくわかってればいいと思います。
KMP：O(N^2)の前処理とO(N)の前処理, Knuth's trick
BM：不一致ルール(bad character rule), 接尾語一致ルール(strong good suffix rule), O(N^2)の前処理とO(N)の前処理, 最悪計算量をO(N)に改善できる
Z-algo：KMP法、BM法の前処理に使える。またKMP,BMと同じくO(N)の検索アルゴリズムとしても機能する

BM法に関しては不一致ルールしか考慮していない記事が多く、接尾語一致ルールに触れている記事もパターンの先頭部分と末尾部分が一致する場合の処理まで言及していない記事が多いです。この解説記事に完全版のBM法がとても詳しく載っています。長いですが流し読みすれば雰囲気はつかめるはずです。

Z-algorithmに関しては、頭が悪くても理解できる記事を見つけるのが大変でした。解説記事が豊富ではなく理解するのが難しいですが、アルゴリズム自体はシンプルです。この解説動画で7分程度の簡単な解説がなされてます。解説の中で一番わかりやすかったです。名前もかっこいいしアルゴリズムもかっこいいので好きです。

苦労して実装しましたが、競プロではローリングハッシュで十分な場面が多そうで使用頻度は低そうです。z-algorithmはたまに便利かもですが。

コードは冗長になりそうなので載せません。Z-algorithmを用いた前処理とか、接尾語一致ルールを取り入れたBM法とか調べた限りない(頑張って探せばたぶんいくらでもある)のでコード載せたら喜ぶ人いるんですかね？そもそもこのブログを見てる人がほとんどいませんが。

2023-04-23

pythonで双対セグ木を書いてみた

競プロやってます。atcoder緑です。双対セグ木のコードを載せます。

区間更新・一点取得が可能なデータ構造があると便利な　この問題　において区間取得できる遅延セグ木だとTLEしたので~~パクリ~~自作しました。(一応上の問題のコードも置いときます)

~
def segfunc(x,y):
    return x+y
#self.lazyは1~indexed
#self.add(l,r,x)は0~indexdの開区間[l,r)
#self.get(i)は0~indexd
class cheapSegTree:
    def __init__(self,n,segfunc):
        self.segfunc=segfunc
        self.num = 1<<(n-1).bit_length()
        self.lazy = [0]*2*self.num
    
    def update(self,l,r,x):
        #下のコードで self.lazy[index]が[l,r)に含まれるindexを網羅できるらしい
        #ノーマルセグ木の区間取得とかでもつかえてすごいけど原理は分からない
        l+=self.num
        r+=self.num
        while l<r:
            if l&1:
                self.lazy[l]=self.segfunc(self.lazy[l],x)
                l+=1
            if r&1:
                self.lazy[r-1]=self.segfunc(self.lazy[r-1],x)
            l>>=1
            r>>=1

    def get(self,i):
        res=0
        i+=self.num
        while i:
            res=self.segfunc(res,self.lazy[i])
            i>>=1
        return res
~

僕の理解(というか予想)では双対セグ木・遅延セグ木においては値を取得するときに蓄積していた更新値を反映した後取得した範囲の更新値を初期化すると思うのですが、上記の問題においては一度取得した範囲は二度と参照しなくてよいので実装を省略しています。というか初期化の仕方はわかりません。
※追記　双対は初期化の必要ないんじゃね？ってなったのでこのコードはれっきとした双対セグ木です。多分

紹介するコードはネットにあった遅延セグ木のコードをいじったものです。元ネタのurlはこちら ←とても参考になります。

緑コーダーが書いたコード・文章なので間違いを含む可能性がとてもあります。

2023-02-27

競プロ | 緑 | 勉強したい項目の羅列

2023/02/27初公開
競プロ、python、atcoder緑。2023/08/30までに青になりたいです。atcoderマイページ
この記事は自分のためのメモですが似た境遇の方の参考になるかもと思い公開。

上から順にこなしていく予定

0. 今取り組んでいること

〆レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】 - Qiita
　　1周したので復習(2/28~3/15)
・Tasks - 競プロ典型 90 問
　　1周したので復習
・Educational DP Contest / DP まとめコンテスト - AtCoder
　　挫折したのでもう一度

1. 過去に学んだことがあり復習したい

・セグ木 : 抽象化遅延セグ木は実装どころかコピペ利用もままならない状態
・multiset、python実装版
・逆元
・最短経路全般
・半分全列挙
・dfs/bfsの行きがけ、帰りがけ
・期待値dp
・bitdp
・区間dp
　　難しすぎませんか
・木dp
・行列累乗によるdp更新高速化

2. 学んだことがなく新しく勉強したい

圧縮、ローリングハッシュ、耳dp、dp高速化のいろいろ、中国余剰定理

3. その他全く知らないけどここやここなどで言及されている項目
平方分割、Grundy数、最大流、最小カット、最小費用、2部グラフ判定、2部マッチング、FFT、強連結成分分解、BIT木、永続配列、SWAG、Dancing Links、ウェーブレット行列、HL分解・オイラーツアー、全方位DP、写像12相、きたまさ法、Berlekamp-Massey、包除原理

ところで本日のABC291、コンテスト終了4秒後にFが通って悲しかったです