恐らくwriterの想定誤解法を順調に踏み抜いた。
http://arc050.contest.atcoder.jp/tasks/arc050_d
問題
N文字の文字列Sが与えられる。
Sの全suffixをそれぞれ1個ずつ連結してできる文字列が辞書順最小となるには、どの順でsuffixを連結すればよいか答えよ。
解法
Suffixという言葉につられてSuffix ArrayのRank順でソートしたりすると失敗する。
「文字列群を連結して辞書順最小にする」という場合、その並べ方は定番テクがある。
(AtCoderでも出たことがあるが、残念ながら問題を失念)
文字列群をソートする際、2つの文字列x,yの並び順を決めたいとき、x+y<y+xならxが前に来るようにすればよい。
T[i] := Sのi文字目以降からなるSのsuffix(S[i..N])とする。
上記アイデアをこの問題に適用すると、2つのsuffix T[L],T[R]があったとき、T[L]+T[R]とT[R]+T[L]の辞書順前後判定が高速行えれば良い。
同じ文字列を何度も前後判定する際、高速に判定する手法としてローリングハッシュと二分探索を用いた方法がある。
文字列A,Bの前後判定をするとき、それぞれ部分文字列のハッシュ値を高速に計算できるようローリングハッシュを前準備しておく。
hash(A[0..k])==hash(B[0..k])となる最大のkを二分探索で求めれば、A[k+1]とB[k+1]は異なるはずなのでA[k+1]とB[k+1]の比較でA,B全体の前後判定ができる。
このテクを使えば、T[L]+T[R]とT[R]+T[L]に対する高速な前後判定ができる。
この前後判定関数をSTLのsort関数の述語に使い、suffixの先頭位置をソートすればよい。
struct RollingHash { static const ll mo0=1000000007,mo1=1000000009; static ll mul0,mul1; static const ll add0=1000010007, add1=1003333331; static vector<ll> pmo[2]; string s; int l; vector<ll> hash_[2]; void init(string s) { this->s=s; l=s.size(); int i,j; hash_[0]=hash_[1]=vector<ll>(1,0); if(!mul0) mul0=10009+(((ll)&mul0)>>5)%259,mul1=10007+(((ll)&mul1)>>5)%257; if(pmo[0].empty()) pmo[0].push_back(1),pmo[1].push_back(1); FOR(i,l) hash_[0].push_back((hash_[0].back()*mul0+add0+s[i])%mo0); FOR(i,l) hash_[1].push_back((hash_[1].back()*mul1+add1+s[i])%mo1); } pair<ll,ll> hash(int l,int r) { // s[l..r] if(l>r) return make_pair(0,0); while(pmo[0].size()<r+2) pmo[0].push_back(pmo[0].back()*mul0%mo0), pmo[1].push_back(pmo[1].back()*mul1%mo1); return make_pair((hash_[0][r+1]+(mo0-hash_[0][l]*pmo[0][r+1-l]%mo0))%mo0, (hash_[1][r+1]+(mo1-hash_[1][l]*pmo[1][r+1-l]%mo1))%mo1); } pair<ll,ll> hash(string s) { init(s); return hash(0,s.size()-1); } static pair<ll,ll> concat(pair<ll,ll> L,pair<ll,ll> R,int RL) { // hash(L+R) RL=len-of-R while(pmo[0].size()<RL+2) pmo[0].push_back(pmo[0].back()*mul0%mo0), pmo[1].push_back(pmo[1].back()*mul1%mo1); return make_pair((R.first + L.first*pmo[0][RL])%mo0,(R.second + L.second*pmo[1][RL])%mo1); } }; vector<ll> RollingHash::pmo[2]; ll RollingHash::mul0,RollingHash::mul1; int N; string S; int ran[101010]; RollingHash rh; pair<ll,ll> getrh(int f,int s,int ts) { if(N-f>=ts) { return rh.hash(f,f+ts-1); } else { return rh.concat(rh.hash(f,N-1),rh.hash(s,s+ts-(N-f)-1),ts-(N-f)); } } int comp(int l,int r) { int len=(N-l)+(N-r); int same=0; for(int i=20;i>=0;i--) if(same+(1<<i)<=len) { int ts=same+(1<<i); if(getrh(l,r,ts)==getrh(r,l,ts)) same=ts; } if(same==len) return 0; char c1,c2; if(l+same<N) c1=S[l+same]; else c1=S[r+(same-(N-l))]; if(r+same<N) c2=S[r+same]; else c2=S[l+(same-(N-r))]; return c1<c2; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S; rh.init(S); vector<int> V; FOR(i,N) V.push_back(i); sort(ALL(V),comp); FOR(i,N) _P("%d\n",V[i]+1); }
まとめ
本番T[L]+T[R]とT[R]+T[L]の大小比較が必要なことはわかりつつも、SAで行けるんではと安易に突っ込んで失敗した。
反例を作るのが難しそうで、手元で検証しなかったんだよね…。
まぁDを本番に解けたの久々だし良かったかな。