AtCoder Beginner Contest 264 G問題 String Fair
問題
提出解答
問題の概要
非空文字列 に対して, の美しさを以下のようにして定める.
- に含まれる連続な部分文字列のうち, に一致する数を としたとき,
美しさは上に有界か? また, 上に有界ならば美しさの最大値を求めよ.
制約
- は長さ 以上 以下の英小文字列
- は全て異なる.
解法
英小文字全体の集合を と書くことにする. に対して, をそれぞれ1文字目が , 2文字目が , 3文字目が であるような長さ の文字列とする.
このとき, をそれぞれ
- となる整数 が存在するならば , 存在しないならば .
- となる整数 が存在するならば , 存在しないならば .
- となる整数 が存在するならば , 存在しないならば .
と定義する.
まず, 長さが であるような文字列に対する美しさの最大値は で求められる.
長さが 以上であるような文字列に対する美しさの最大値を求める. 長さが 以上の文字列 に対して, の美しさを とすると, の美しさは の末尾2文字を としたとき,
である.
また, 長さが の文字列 の美しさは である.
これらのことから, 次の解法が正当性を持つということもわかる.
- 重み付き有向グラフ を以下で設定する.
- を以下で定める.
このとき, 長さ 以上の文字列における美しさの最大値は における を始点, を終点とする最大重み walk の重みである.
これを求めるために, の値域としては正と負両方があり得るので Dijskra 法を使うことはできない. そこで別の方法を用いることにする. 今回, において頂点数は , 辺の数は約 個であるから, Bellman-Ford 法を利用することにより, 重みが正の閉路の検出もでき, それが存在しない場合の最大重み walk の重みも 時間で求めることができる.
長さ と長さ 以上の結果を合わせることによって最終解答を導くことができる. 時間計算量は 時間である.