Document

Problem B: Kth-Sentence
原案：岩田
解答：岩田、須藤
解説：須藤
問題概要
 n個の単語が与えられる
 単語を並べてできる長さmの文字列のうち
辞書順K番目のものを求める
m
≦ 2000, n ≦ 100, K ≦ 1018
各単語の長さは200以下
解答概要(1/2)
 dp[i]
: 生成できる長さiの文字列の個数
 DPによりO(nm)で求めておく
 先頭から1文字ずつ決めていく
 現在の文字列をSとする
 文字cについて、S’=Sc
よりも辞書順で小さい文字
列がK個以下になる最小のcが次の文字になる
解答概要(2/2)
 文字列S’よりも辞書順で小さいものの数
 num[i]
: S[0, i) となる単語の並べ方の数
 単語wiの先頭j文字がSの接尾辞となるものについて
num[|S|-j] * dp[m-(|S|-j+|wi|)] の和を取る
 オーバーフローに要注意
 次の文字が決まったらnumを更新する
 num[|S’|]
= Σ{wはS’の接尾辞}num[|S’|-|w|]
計算量
 全体でO(mn|w|)になる
 wi[0,j)
が S’=Sc の接尾辞になっているかは,
Sとの比較結果や、ローリングハッシュを使うと
定数時間で判定可能

Download Report