数字列をカンマで分ける問題(CODE FESTIVAL2016 ETR1B)について
問題内容は以下で。
https://atcoder.jp/contests/cf16-tournament-round1-open/tasks/asaporo_f
解説と全然解き方が違ったので書いておきます。
-
解説
答えの候補が高々N通りだから、にぶたんでシミュレートすれば(文字列比較をsuffix arrayでO(1)で出来るようにすればO(NlogN)で解けるよね！
-
僕
文字列長が320以下なら答えの候補が高々10^320≒2^1000だからにぶたんしてシミュレートすれば1000*Nぐらいで通るよね！
逆に文字列長Lが320より上なら取るべき区間の数Kが320以下になるから、文字列比較にO(L)かけたとしてもDPでO(LK^2)≒O(NK)で通るよね！
