okura diary

おもに競技プログラミングの日記

Educational Codeforces Round 97

DP Aho-Corasick HLD ECR

Dashboard - Educational Codeforces Round 97 (Rated for Div. 2) - Codeforces

E: Make It Increasing

列を区切ってLISすればOK

Submission

F: Emotional Fishermen

順列の数え上げだし挿入DPだろうと決め打って考えたが解けなかった。この問題はよくある挿入DPのようにソートして昇順or降順に要素を埋めながら列を構成するというよりは、前から順に好きな要素で埋めていくという方法がうまくいく。

\displaystyle dp[ i + 1 ][j] := i\mbox{番目までの順列で、最大値が}a_j

として最大値が更新される場合とそうでない場合の遷移を考える。累積和を使って高速化すると O(N^2)

Submission

G Death DBMS

明らかにAho-Corasickを使ってくれという感じの問題なので使う。するとSuffix Linkからなる木上で、各頂点から根までの最大値を求めるクエリにたくさん答えたくなるのでHLDで殴った。 Editorialで賢い方法が紹介されていた。文字列集合が重複なしであるとすると、Aho-Corasick automatonのあるstateにマッチしうる文字列(suffix linkを辿っていってマッチするもの)の種類数は O(\sqrt{\mbox{文字列の長さの和}})で抑えられる。なぜかというと各長さの文字列についてマッチしうるのは高々一つなので、 1+2+...+k \leq \mbox{長さの和}となるからである。なので木をexit linkで愚直に根まで辿っていっても O(Q\sqrt{N})程度で通る。

Submission