More Related Content
Viewers also liked (19)
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
会津合宿2015顿补测3：贵问题
- 2. 問題概要 ? 文字列Sが与えられる ? S = ABABAとなるような非空文字列A, Bがある か判定せよ ? あるなら|AB|が最小になるものを出力せよ ? 制約: 1 ≤ S ≤ 106
- 3. 想定 TLE 解法: 全探索 ? Aの長さを決め打ちする (1 ≤ |A| ≤ |S|/3) ? するとBの長さは一意 (B = (|S| - 3|A|) / 2) ? あとは以下が一致するか調べればよい ? S[0:A) と S[A+B:2A+B) と S[2A+2B:3A+B) ? S[A:A+B) と S[2A+B:2A+2B) ? O(N)通りについて、長さO(N)の文字列比較を行 うのでO(N2)? → N = 106なのでTLE
- 4. 想定解法: ローリングハッシュ ? 部分文字列 s[l:r) に以下のようなハッシュ 値h(l,r)を割り当てる ? h(l,r) = Σl≤i≤r (int)si * p(r-i) mod M ? p, Mは互いに素 (基本p<Mで、素数とか) ? このハッシュ値が一致 ? 文字列が一致
- 5. 想定解法: ローリングハッシュ ? h(l,r) = Σl≤i≤r (int)si * p(r-i) mod M ? このハッシュ値が一致 ? 文字列が一致 ? つまり……以下を調べればよい ? h(0,A) = h(A+B,2A+B) = h(2A+2B,3A+2B) ? h(A,A+B) = h(2A+B,2A+2B) ? 数値なのでO(1)で判定できる ? ただし、ハッシュ一致 ? 文字列一致は言えない ? まともな p, M を使えば確率的にほとんど起こ らない
- 6. 想定解法: ローリングハッシュ ? h(l,r) = Σl≤i≤r (int)si * p(r-i) mod M ? けど h を計算するのに O(N) かかるのでは？ ? h(l,r) = (h(0,r) - h(0,l) * p(r-l)) mod M ? h(0,i) = h(0,i-1) * p + (int)si? と計算できるので、あらかじめ h(0,i) を O(N)で計算しておけば h(l,r) の計算は O(1) ? 全体で O(N)
- 7. 別解: Suffix Array + LCP + RMQ ? 接尾辞配列 (SA) を作り、SAで隣との共通部分接 頭辞 (LCP)の長さを記録した配列に対して区間最 小値クエリ (RMQ) を投げる ? S[l1,l1+k) と S[l2, l2+k) の文字列比較をすると きは、l1とl2に該当するSAのインデックスを区間と してRMQすると、答えがl1,l2の共通接頭辞の長さに なる ? これがkより長ければS[l1,l1+k) = S[l2, l2+k) ? 計算量: O( SA構築 + NlogN ) ? 蟻本のSA構築は O(Nlog2 N) なのでTLE的に厳しい
- 8. 余談 ? ぶっちゃけナイーブO(N2)が速すぎたので? |S|≤106になった ? のでSA+LCP+RMQは厳しくなった ? 个人的にはこっちもすんなり通したかった
- 9. ジャッジ解 ? 井上 (C++) 54行 1057B ? 鈴木 (C++) 38行 1035B ? 田中 (C++) 43行 1331B
- 10. 回答状況 ? Accept / Submit ? 11 / 30 (36.7%) ? First Acceptance ? onsite: syumi_plus (01:53) ? online: natsugiri (00:24)