HackerRank World CodeSprint 7

各値の出現頻度を数えてそれぞれ 2 で割って足し合わせる。

2 文字を全探索しても O(26² n)。

行ごとに区間を振り分けて、それぞれの行で区間に覆われている長さを求めよう。座圧して imos もできるけど、追加・削除イベントを配列に入れてシミュレーションが個人的には楽。

ものすごく面倒だったんだけど良い解法あるのかな…？闇なので説明できません。

distinct な数列で RMQ を構築しているので、各値の影響範囲というのは以下のようになる。

f:id:pekempey:20160926234353p:plain

上図より、サイズ 8 のセグメント木の場合、頻度1が4つ、頻度2が2つ、頻度3が1つ、頻度4が1つということが分かる。

この情報を元に貪欲に当てはめればいい。

[L,R]をすべて録画できるかの判定が高速にできれば尺取法が使える。

区間 i の live 側を取るかどうかを表す変数を xi とする。もし区間 i(live) と区間 j(live) が重なっていたら $\lnot x_i \lor \lnot x_j$ が真でなければならない。

これをすべての i,j に対して考えると 2-SAT になることが分かる。

2-SAT は強連結成分分解を用いて O(n+m) で解けるため全体で O(n³) となる。q=100 ってのがあるけど、100⁴くらいなら通る。

文字列 S と文字列 T が似ているというのは、S の文字割当を入れ替えて T と等しくできるということを意味する。

たとえば S=abacc, T=babdd だったら、S の文字割当を (a,b,c,d)→(b,a,d,c) のように置換すれば等しくなるので S と T は似ている。

似ているかどうかを簡単に判定するために正規化という操作を導入する。

文字列の正規化というのは、1番最初に現れた文字を a に、2番目に現れた文字を b に…、という感じで文字割当を置換する操作である。

たとえば S=giggabaj の場合、まず g が現れるので g→a とする。次に i が現れるので i→bとする。このように順次処理をしていくと正規化後の文字列は norm(giggabai)=abaacdcb となる。

SとTが似ているということと norm(S)=norm(T) であることが同値であることは明らかだろう。

さて話は飛ぶが、文字列 S が与えられて、その部分文字列 S[L..R] が S の中に何個あるかを数える問題を考える。元の問題はこの問題を難しくしたものと見て取れるため、この問題を解くことには意味がありそうである。

問題を解く鍵となるのが suffix array と LCP である。接尾辞 S[L..] との LCP が R-L+1 以上であるものの個数を数えればよくて、これは SA 上で二分探索することで知ることができる。

正規化された接尾辞で SA を構築すればいい。

この問題では蟻本に書いてある手法や SA-IS のような suffix array のアルゴリズムは恐らくだが使えない。よく分からないので rolling hash でソートしよう。

文字置換後のハッシュ値を高速に計算する必要がある。ハッシュ値は $h_a a + h_b b + h_c c + \cdots + h_j j$ のようになっているので、$h_a,h_b,h_c,\ldots$ だけを計算しておけばいい。

計算量は O(10 n log² n) であり、愚直な O(N²) より少し軽いくらいなので定数倍で速くないと TLE する。

rolling hash による LCP はひたすら重いので呼び出し回数を減らしたい。構築時の LCP はどうしようもなさそうだが、SAが一度構築できてしまえば sparse table による LCP に切り替えられるのでクエリの方の負担は軽くできる。

かなり定数倍がきつくて mod 1 つでもギリギリだったが何とか通すことはできた。これ想定解なんだろうか…？

いつもだったら n-1 完でも 100 位以内から追い出されるけど今回は普通に通った。うーん。