LeetCode Weekly Contest 137

LeetCode Programming Contest

5/19(日) 11:30-13:00

4完ノーペナで102/4091位
ノーペナは嬉しい（ちょっと慎重になりすぎて遅かったかも）

2019-05-19

Google Code Jam 2019 Round 2

Google Code Jam Programming Contest あとで書く

5/18(土) 23:00-25:30

B(interactive問題)の1完のみ23点で1231位。R3進出（＆TシャツGET）ならず。
R1のinteractiveも3問とも(R1A,R1B,R1C)解いたけど、今年のinteractiveはすごく自分向きだった。

（あとで書く）

2019-05-13

Suffix Array（接尾辞配列）とLCP（最長共通接頭辞）arrayを線形時間で構築する方法を調べてみた〜SA-ISとKasai's algorithm〜

Algorithms memo

suffix arrayは知ってます。（当然）
（知ったきっかけは何だったかな…高林さんのsaryかな）
以前、英辞書検索用のCLIツールを作る時などにも使いました。

でも今までずっと、文字列のポインタを1つずつずらした（文字列の長さ分の）char**配列を用意してqsortでstrcmp的なものを渡すような、愚直な（ $O(N^2\log N)$ の）書き方しかしたことがありませんでした。

あまりそれで困るような場面に遭遇したことがなかったということでもありますが、
競プロで使うとなるとそういうわけにはいきません。

制約が $N=|S|=10^5$ とかだともう無理ですよね。

LCP（最長共通プレフィックス）array もそうです。
suffix arrayを作った後に、隣り合う項目同士の最長共通プレフィックスを求めておくやつです。
隣同士の最長共通プレフィックスのリストがあると、あとはRMQとか使えば任意の2つのサフィックスの共通プレフィックスが求められたりして便利（らしい）です。
（配列の長さ-1）組の文字列の比較なので普通に考えたら $O(N^2)$ かかります…よね*1。

なのに、 $N=10^5$ なのにいかにもsuffix arrayとLCP（最長共通プレフィックス）arrayを計算して下さいと言わんばかりの問題*2が来て、上位陣はsuffix arrayで通しているというのです。

そこで

O(N)でsuffix arrayが構築できる方法

と

O(N)でLCP arrayが構築できる方法

について調べてみました。

上級者の皆様には「そんな事も知らなかったのか」「蟻本（上級編）に書いてあるぞ」「蟻本読め」「蟻本」と思われることでしょうが青コーダーレベルだと今までそれで困る場面がなかったということでお許しください。

*1:蟻本上級編を読めというお叱りはあとで受けます。

*2:毎週日曜開催の某コンテストで最近そんな問題が出ました。

2019-05-12

LeetCode Weekly Contest 136

LeetCode Programming Contest

5/12(日) 11:30-13:00
とあるTully'sにて
Dを通せないまま途中離脱(3完1ペナ)；
143/4109位
3完の割にひどい順位にならなかったのはQ4通した人数が少なかったから（全完92人）
それでもレートは微増：2306→2309
f:id:n4_t:20190514121829p:plain:w320
World Rankingは144 / 95530