読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

CODE FESTIVAL 2016 Elimination Tournament Round 1 B. 数字列をカンマで分ける問題

AtCoder Suffix Array 二分探索

解法

均等にカンマを挿入するのが最もよく、このとき答えの長さはL=ciel(|S|/K)=(|S|+K)/(K+1) である*1

よって、長さがLの|S|-K+1 通りの部分文字列を考えればいい。
ある長さがLの文字列xが答えになるかどうかは、前からL文字がx以下であればL文字進めて、xより大きければL-1文字進める、を末尾まで繰り返して、進めた回数がK+1回以下かどうかで調べられる。
ただしこれは、O(|S|^2)かかるのでTLEする。

どうすればいいかというと、答えを二分探索すればよい。
しかし、長さ|S|の数字はlong longでも足りないし、長さLの|S|-K+1通りの文字列を全部取ってくるだけでO(|S|^2)かかりTLEするので、Suffix Arrayを構築すればよい。*2
よってSから構築したSuffix Array上を二分探索すればよい(ただし長さがL以下のsuffixは取り除く)。

あとはやるだけであるが、二分探索の際に、あるxに対して、長さLの部分文字列がx以下かどうかは、(この場合は)suffix arrayを構築しているので(蟻本でいうと)rankを用いて簡単に求められる。

計算量

O(|S| log |S| + |S| log^2 |S|)
(2項目はsuffix arrayを構築の計算量)

コード


感想

  • 解法は帰りの電車で分かってたけど、やっとコード書いた
  • やっぱりsuffix array使う問題は考察が重い
    • suffix array上で二分探索とかしたことなかったので頭に入れときたい

*1:答えをL-1にできないことは、(L-1)*(K+1) < |S|になることを考えれば自明

*2:しかしpython多倍長整数を使えばACは可能 http://cf16-tournament-round1-open.contest.atcoder.jp/submissions/1003624