CTT 2019 Day 1 B 异世界的文章分割者

JOI 本選で負けて発奮したので、 OI に向けて頑張るというなら中国の問題も解こう！と言って CTT 2019 を開いたら打ちのめされている。このレベルを 3 問とは… という感じ。参加者が実際にどれくらいの点数を取ったのか気になる。とりあえずこの問題に 1 日費やしたのでそれについて書く。

問題概要
- ところで
解法
感想

問題概要

問題リンク (QOJ)
整数 $n, k \ (1 \leq k \leq n)$ と長さ $n$ の文字列 $s$ が与えられる。
長さ $m$ の文字列 $t$ に関するコスト関数 $\mathrm{value}(t)$ を以下のように定義する。

$\displaystyle \mathrm{value}(t) = \sum_{i=1}^{m-1} (w(T[1:i], T[i+1:m])^2$

ここで $2$ つの文字列 $a, b$ について $w(a, b)$ は unique な共通部分文字列の個数。(空文字列を除く)

$s$ を $k$ 個の部分文字列に分解して、各部分文字列に関するコストを考えたとき、その最大値として可能な最小値を出力せよ。

制約 : $1 \leq k \leq n \leq 5 \times 10^4$ で、 $s$ はアルファベット小文字からなる。
$n = 10, 50, 200, 1000$ に部分点がある。TL が 8s と長い。

ところで

ChatGPT に中国語を Chrome からコピペして翻訳をお願いすると、数式でフォーマットや改行がぐちゃぐちゃでも割と翻訳してくれます。中英の方が中日より精度がよい気もするがどちらでもなんとかなります。GPT4o は数問翻訳させると初めの指示を忘れて考察を書いてきたので、毎回指示をコピペするとよいです。

解法

本質以外

かなりコスト関数が難しそうで困る。$2$ 乗されているので、たまにあるコスト関数を賢く解釈して分解？みたいなこともできなさそう。わざわざ $2$ 乗しているというのはそういうことなんだろう (メタ読み)
そうとなると、変な性質を追加で見つけない限りは、 $l$ を固定したときに $r = l, l + 1, \dots ,n$ について $\mathrm{value}(l, r)$ を求めるのすら、最後の $2$ 乗して集計するパートだけで $O(n^2)$ かかってできなさそう。
制約が小さいので、 $\sqrt{n}$ みたいな項を混ぜながらうまく誤魔化したくなるが (なった) 、なんともならなかった。

数時間が経過したので人の提出をチラ見してびっくりした。結局長さ $m$ の文字列に対してコスト関数を $O(m\sigma)$ (ここで $\sigma = 26$ は文字種数) で計算できる。これができれば解けるのはそれはそうで、答えを二分探索して更に内部でも二分探索して $O(n \sigma \log^2 n)$ で解ける。

fn calcCost(s: int) -> int :
    // がんばる

fn isPossible(threshold: int) -> bool:
    l = 0
    cntRanges = 0
    while l != n:
        r = l
        cntRanges += 1
        for i: (0, 20):
            if calcCost(s.substr(l, r + (1 << i))) > threshold:
                for j: reverse (0, i):
                    if calcCost(s.substr(l, r + (1 << j))):
                        r += (1 << j)
        l = r
    return cntRanges >= k

fn solve():
    ok = inf, ng = 0
    while ok - ng > 1:
        mid = (ok + ng) / 2
        if (isPossible(mid)) ok = mid
        else ng = mid
    return ok

Suffix Automaton

大道具 Suffix Automaton を取り出す。CP-Algorithm の記事と数時間にらめっこした。(わかりやすいのは間違いないのでおすすめです)

Suffix Automaton は気持ちをしっかり理解しないと応用で使えない感じがする。例えば

文字列 $S, T$ が与えられる。これらの unique な共通部分文字列の個数を数え上げよ。

という問題を考えてみる。これを Suffix Automaton を活用？して解こうとするといくつか方法がある。(方針としては正しいと思いますが細部が違うかもしれないです)

$S, T$ の間に仕切り文字を加えて、 $S, T, S\text{#}T$ それぞれについて部分文字列を数え上げる。それぞれ $a, b, c$ としたとき、 $a + b \mathrel{-} (c \mathrel{-} (|S| + 1) \times (|T| + 1))$ が答え。
オートマトンなことを思い出して、 $S, T$ どちらの部分文字列も受理するオートマトンを構築する。それぞれのノードに $S, T$ それぞれの部分文字列であるかというフラグを加えて、どちらのフラグも正であるものについて $\mathrm{len}(v) \mathrel{-} \mathrm{len}(\mathrm{link}(v))$ を足した和が答え。
$S$ から Suffix Automaton を作る。今マッチしている最大の長さ $l$ を保持しながら $T$ を $S$ に走らせて、各ノードに $l$ の最大値をメモする。この情報を用いてなんとかする。

(上 2 つは yosupo さんのブログより)

自分は CP-Algorithm の記事の Application 欄の問題とこれらのそれぞれを、記事内の図と一緒ににらめっこすることで気持ちを理解した (つもり)。とにかく図を見て頭の中の思い込みを修正するという作業を 20 回くらいした。

コスト計算

とにかく一番重要なのは、各状態がある文字列 $w$ の長さ $l$ 以上の suffix という形でそれぞれ unique な部分文字列の情報を保持していること。これをちゃんと思い出す。
文字列 $s$ のコストを求めたいとする。今回の問題は各状態に以下のように情報を付け足せる。

対応する文字列が $s$ の部分文字列として出てきた最初の位置と最後の位置 (複数の文字列が $v$ に含まれるが、部分文字列の終端の index を保持すると一意)

これは、最初に Suffix Automaton を構築するタイミングで $s[1: i]$ に対応する状態に $(i, i)$ をメモしてから、 link の木の上で DP をして全てのノードに情報を行き渡らせればよい。

構築が終わったら今度は各状態についてその寄与を見ていく。
ある状態 $v$ が長さ $\mathrm{minLen}$ 以上 $\mathrm{maxLen}$ 以下の状態を保持しており、 $s$ 上での最初の位置が $x$ で最後の位置が $y$ だとする。そのとき、 $s[1 : i], s[i + 1 : n]$ が状態 $v$ の表す部分文字列のうちいくつを共通で持つか？を考えると、

$x \leq y \mathrel{-} \mathrm{maxLen}$ の場合 (つまり、長さ $\mathrm{maxLen}$ の文字列をどちらも含むことが可能なとき
- $x \leq i \leq y \mathrel{-} \mathrm{maxLen}$ なら $\mathrm{maxLen} \mathrel{-} \mathrm{minLen} + 1$ 個
- $y \mathrel{-} \mathrm{maxLen} < i \leq y \mathrel{-} \mathrm{minLen}$ なら $\mathrm{maxLen} \mathrel{-} \mathrm{minLen} + 1 \mathrel{-} (i \mathrel{-} (y \mathrel{-} \mathrm{maxLen}))$ 個
- どちらにも当てはまらない場合 $0$ 個
そうでない場合
- 最初のパートが消えて、線形に減っていくパートだけ残る、あるいはどの $i$ にも寄与しないことになるが、するべきことは同じ

これらの形で表される寄与をまとめて計算すればよい。

静的な区間加算と区間線形加算ができればよいので、 imos 法を 2 重に用いる。これで各 $i$ について $s[1 : i], s[i + 1: n]$ の共通部分文字列の数え上げができる。コスト関数は二乗和なのでその通り実装すると、コスト関数を $O(n \sigma)$ で計算できる。

自分の提出

感想

Suffix Automaton を勉強したことがあって鮮明な知識があるという前提で、実装込みの難易度 11 だと思う。最初のパートでほとんど全員が脱落しそう。

そもそも IOI シラバスは文字列アルゴリズムに厳しいので、中国はどういうレギュレーションでやっているのか気になる。(おそらく、JOI 春以上に、名実共になんでもありなのだとは思う)