狠狠撸

狠狠撸Share a Scribd company logo

Kth

?
?
O
oupc
1 of 11
Download to read offline
K-th String 原案：komiya, lyoz 解答：komiya, lyoz スライド：komiya
問題概要 ● 長さNの文字列で、suffix arrayが与えられたもの と等しくなるようなもののうち、辞書順でK番目にく るものを求める問題。 ● N≦10^5 ● K≦10^18 ● アルファベットサイズ=:A≦26
観察：数え上げ ● まず、与えられたSuffix Arrayが出てくるような文 字列がいくつあるか数え上げてみよう。 ● inv[sa[i]] = iとする。 ● S[sa[i]] ≦ S[sa[i+1]]が必要。 ● 上の式で、inv[sa[i]+1] > inv[sa[i+1]+1]なら等 号をつけてはならない。 ● 理由：文字列x, yについてx[1]=y[1]なら 　x≦y ? x[2..]≦y[2..]
観察：数え上げ ● 具体的に、sa[] = {2,5,1,3,4}とする。 ● このとき、S[2]≦S[5]≦S[1]≦S[3]≦S[4]が必要。 ● S[2]=S[5]のとき、S[3..]<S[6..]=””である必要が あるが、これは成り立たない。なのでS[2]<S[5]。 ● S[5]=S[1]のとき、S[6..]<S[2..]である必要がある が、これは正しい。なのでS[5]≦S[1]。 ● 同様にやって、S[2]<S[5]≦S[1]≦S[3]<S[4]。 ● これは必要十分。
観察：数え上げ ● 結局、以下のような場合の数に落ちる。 ● 白い玉がN個と黒い玉A-1個を一列に並べる。 ● ただし、inv[sa[i]+1]>inv[sa[i+1]+1]ならi番目の 白玉とi+1番目の白玉の間に少なくとも1個の黒 い玉を置く必要がある。 ● このような白玉、黒玉の列と文字列が対応してる。 S[sa[i]]= {'a' + (i番目の白玉の左側にある黒玉の個数)}
観察：数え上げ ● 「必ず黒玉をおかなきゃならない位置」を考えるの は面倒なので、そのような箇所がu個あるとき、そ のu個を最初から取り除いて考える。 ● つまり、白玉N個と黒玉A-1-u個を自由に並べて、 その後黒玉u個を該当箇所に追加すると考える。 ● これだと、白玉N個と残りの黒玉A-1-u個を制約 なく一列に並べる場合の数になり、 combination(N+A-1-u, A-1-u) が答えとなる。
解法 ● 「辞書順最小を求めよ」の典型パターンと同じよう に解く。 ● 先頭から順に、「この文字に確定したら何通りの 文字列が作れるか」を計算して1文字ずつ進めれ ばよい。 ● さっきと同じように、「黒玉をおかなきゃならない位 置」は最後に考えるようにすると楽。
解法 ● i文字目を固定するとき、残りの文字の決め方が何 通りあるかを効率的に計算したい。 ● A-1-u=10で、4文字目までは確定している場合。 i 0 1 2 3 4 5 6 7 8 sa[i] - 4 2 5 6 1 3 7 - 黒玉の累積値 0 2 2 未 未 7 10 未 10 ● 上の場合は、区間[(2,5),(6,8)]を持っておく。それ ぞれの区間は互いに干渉しない。
解答 ● 「両端の累積値が固定された区間」同士は互いに 独立に考えてよい。 ● 各区間ごとに、「白玉と黒玉を一列に並べる場合 の数」を計算しておいて、その区間の列を持ってお く。 ● i文字目を固定したときの場合の数は、新たに区 間のひとつを分割してそれぞれの場合の数の積 が何通りになるか計算すればよい。
高速化 ● これを愚直にやると、区間の数がO(N)個になりう るので全体でO(N^2)となりうまくいかない。 ● しかし、自由度のある区間は高々A個しかない。 ● なので、自由度の存在しない区間については保持 しないようにする。 ● こうすることで、O(N*A)となり間に合うようになる。
注意点 ● 全体として、積をとる場面でオーバーフローがおき うるので、以下のような関数を用意しておくと楽。 　long mul(long x, long y) { return (double)x*y>INF?INF:x*y; } ● 二項係数の計算は、パスカルの三角形を使えば 前処理で必要な分を全部計算しておける。

More Related Content

Kth

  • 2. 問題概要 ● 長さNの文字列で、suffix arrayが与えられたもの と等しくなるようなもののうち、辞書順でK番目にく るものを求める問題。 ● N≦10^5 ● K≦10^18 ● アルファベットサイズ=:A≦26
  • 3. 観察：数え上げ ● まず、与えられたSuffix Arrayが出てくるような文 字列がいくつあるか数え上げてみよう。 ● inv[sa[i]] = iとする。 ● S[sa[i]] ≦ S[sa[i+1]]が必要。 ● 上の式で、inv[sa[i]+1] > inv[sa[i+1]+1]なら等 号をつけてはならない。 ● 理由：文字列x, yについてx[1]=y[1]なら 　x≦y ? x[2..]≦y[2..]
  • 4. 観察：数え上げ ● 具体的に、sa[] = {2,5,1,3,4}とする。 ● このとき、S[2]≦S[5]≦S[1]≦S[3]≦S[4]が必要。 ● S[2]=S[5]のとき、S[3..]<S[6..]=””である必要が あるが、これは成り立たない。なのでS[2]<S[5]。 ● S[5]=S[1]のとき、S[6..]<S[2..]である必要がある が、これは正しい。なのでS[5]≦S[1]。 ● 同様にやって、S[2]<S[5]≦S[1]≦S[3]<S[4]。 ● これは必要十分。
  • 5. 観察：数え上げ ● 結局、以下のような場合の数に落ちる。 ● 白い玉がN個と黒い玉A-1個を一列に並べる。 ● ただし、inv[sa[i]+1]>inv[sa[i+1]+1]ならi番目の 白玉とi+1番目の白玉の間に少なくとも1個の黒 い玉を置く必要がある。 ● このような白玉、黒玉の列と文字列が対応してる。 S[sa[i]]= {'a' + (i番目の白玉の左側にある黒玉の個数)}
  • 6. 観察：数え上げ ● 「必ず黒玉をおかなきゃならない位置」を考えるの は面倒なので、そのような箇所がu個あるとき、そ のu個を最初から取り除いて考える。 ● つまり、白玉N個と黒玉A-1-u個を自由に並べて、 その後黒玉u個を該当箇所に追加すると考える。 ● これだと、白玉N個と残りの黒玉A-1-u個を制約 なく一列に並べる場合の数になり、 combination(N+A-1-u, A-1-u) が答えとなる。
  • 7. 解法 ● 「辞書順最小を求めよ」の典型パターンと同じよう に解く。 ● 先頭から順に、「この文字に確定したら何通りの 文字列が作れるか」を計算して1文字ずつ進めれ ばよい。 ● さっきと同じように、「黒玉をおかなきゃならない位 置」は最後に考えるようにすると楽。
  • 8. 解法 ● i文字目を固定するとき、残りの文字の決め方が何 通りあるかを効率的に計算したい。 ● A-1-u=10で、4文字目までは確定している場合。 i 0 1 2 3 4 5 6 7 8 sa[i] - 4 2 5 6 1 3 7 - 黒玉の累積値 0 2 2 未 未 7 10 未 10 ● 上の場合は、区間[(2,5),(6,8)]を持っておく。それ ぞれの区間は互いに干渉しない。
  • 9. 解答 ● 「両端の累積値が固定された区間」同士は互いに 独立に考えてよい。 ● 各区間ごとに、「白玉と黒玉を一列に並べる場合 の数」を計算しておいて、その区間の列を持ってお く。 ● i文字目を固定したときの場合の数は、新たに区 間のひとつを分割してそれぞれの場合の数の積 が何通りになるか計算すればよい。
  • 10. 高速化 ● これを愚直にやると、区間の数がO(N)個になりう るので全体でO(N^2)となりうまくいかない。 ● しかし、自由度のある区間は高々A個しかない。 ● なので、自由度の存在しない区間については保持 しないようにする。 ● こうすることで、O(N*A)となり間に合うようになる。
  • 11. 注意点 ● 全体として、積をとる場面でオーバーフローがおき うるので、以下のような関数を用意しておくと楽。 　long mul(long x, long y) { return (double)x*y>INF?INF:x*y; } ● 二項係数の計算は、パスカルの三角形を使えば 前処理で必要な分を全部計算しておける。