CODE FESTIVAL 2016 Elimination Tournament Round 1 B. 数字列をカンマで分ける問題
解法
均等にカンマを挿入するのが最もよく、このとき答えの長さは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