naoya_t@hatenablog

いわゆるチラシノウラであります

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

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)でLCP arrayが構築できる方法

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

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

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

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

続きを読む

Google Code Jam 2019 - Qualification Round

4/6(土)08:00 - 4/7(日)11:00
Qualに限って相談OKなので、有志4人で集まって電源wifi完備なカラオケルームを借りて参加*1
f:id:n4_t:20190406111753j:plain:w320f:id:n4_t:20190406115749j:plain:w320
全員予選通過ライン(30点)は超えられたので目的は果たせたかと

会場でD-smallまで解いて(提出は帰宅後)
その後D-largeも解いて終了。

終了後ジャッジでLargeも全て通って100点満点
f:id:n4_t:20190407110603p:plain
次はRound 1でお会いしましょう。

【参考資料】当日のセットリスト(誰がどれを歌ったかは秘匿)
docs.google.com

*1:1AC→1曲歌ったら次の問題に進める

続きを読む

多倍長整数問題はPythonで

Joeくんが言及してたやつ


yukicoder No.381 名声値を稼ごう Extra

No.381 名声値を稼ごう Extra - yukicoder

言語の特性上C++,Java,C#で正答するのは困難かもしれません。Ruby,Pythonでの回答をおすすめします。

続きを読む

全国統一プログラミング王決定戦 本戦

atcoder.jp
主催/日本経済新聞社 共催/AtCoder 協賛/TRI-AD,CISCO
2/17(日) @東京ドームホテル 大宴会場「天空」
f:id:n4_t:20190217151752j:plain

予選500位に入ったので決勝大会後のイベント&懇親パーティーに呼ばれて参加してきました。
f:id:n4_t:20190218181009j:plain
問題文は最初公開されていなかったのだけれど、本戦終盤頃にPDFで公開されたのでKindleに入れてちびちび考えていました。*1

chokudai社長 + PFNの秋葉さん西川さんのトークショーの後、上位3名によるエキシビション(20分8問のコンテスト形式+chokudai氏の実況)があって凄く面白かったし刺激的でした。
8問全完した準急さんのキー入力はめちゃ速いです。

500人懇親パーティーは美味しい食事+色々な人と話せて楽しかったです。
f:id:n4_t:20190217194643j:plain:w400
というわけで、本戦+エキシビションの問題を見ていこうと思います。

*1:本番ではネットワークトラブル回避のため問題文が紙で配られたそうです。

続きを読む

ゆるふわ競プロオンサイト @FORCIA

forcia.connpass.com
2/9(土) 14:00-

FORCIAさんで開催されたオンサイトのゆるふわコンテストに参加。
(over28枠に空きが1つ出たのを知って前日に登録)
最初404が出てコンテストがなかなか始められず(CTF?)、HackerRankでコンテスト開催経験のある人が呼ばれて対応に当たっていた…
そして15分遅れて(URLを変更して)コンテスト開始。
100-200-300-400-500-600-700-800 という配点と問題の体感難易度が大きくずれていた気がする。
4完(+部分点)で27位とかそのくらい。
Programming Problems and Competitions :: HackerRank

コンテストだけ出て懇親会は(ピザonlyであることが知られているので)帰るつもりだったけど、皆さんと色々話してて結局懇親会の最後(19:00)まで滞在。(お菓子と飲み物があって助かった)
FORCIAさん@matsu7874さんどうもありがとうございました。

続きを読む

Educational DP Contest / DP まとめコンテスト〈EDPC〉補習篇(T,U,V,W,X,Y,Z)

コンテスト後に読んだ問題たち。ここで出てくるテクニックもこの機会にぜひ身につけておきたい。

参考:
www.hamayanhamayan.com
kyopro-friends.hatenablog.com
↑競プロフレンズさんてチームで戦ってるの?それって規約的にどうなの?*1

*1:嘘ですこないだDDCC Finalで御本人拝見しました

続きを読む

DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦

1/19(土) 9:00-18:20
株式会社ディスコ

楽しかった
今回は辞退せず参加して良かった

続きを読む