Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 264 G問題 String Fair

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

非空文字列  S に対して,  S の美しさを以下のようにして定める.

  •  S に含まれる連続な部分文字列のうち,  T_i に一致する数を  \chi_S(T_i) としたとき,  \displaystyle \sum_{i=1}^N \chi_S(T_i) \times P_i

美しさは上に有界か? また, 上に有界ならば美しさの最大値を求めよ.

制約

  •  1 \leq N \leq 18278 (=26+26^2+26^3)
  •  T_i は長さ  1 以上  3 以下の英小文字列
  •  T_i は全て異なる.
  •  -10^9 \leq P_i \leq 10^9

解法

英小文字全体の集合を  \mathcal{A} と書くことにする.  \alpha, \beta, \gamma \in \mathcal{A} に対して,  \alpha, \alpha \beta, \alpha \beta \gamma をそれぞれ1文字目が  \alpha, 2文字目が  \beta, 3文字目が  \gamma であるような長さ  1,2,3 の文字列とする.

このとき,  S_{\alpha}, S_{\alpha \beta}, S_{\alpha \beta \gamma} をそれぞれ

  •  T_i=\alpha となる整数  i が存在するならば  S_{\alpha}=P_i, 存在しないならば  S_{\alpha}=0.
  •  T_i=\alpha \beta となる整数  i が存在するならば  S_{\alpha \beta}=P_i, 存在しないならば  S_{\alpha \beta}=0.
  •  T_i=\alpha \beta \gamma となる整数  i が存在するならば  S_{\alpha \beta \gamma}=P_i, 存在しないならば  S_{\alpha \beta \gamma}=0.

と定義する.

まず, 長さが  1 であるような文字列に対する美しさの最大値は  \displaystyle \max_{\alpha \in \mathcal{A}} S_{\alpha} で求められる.

長さが  2 以上であるような文字列に対する美しさの最大値を求める. 長さが  2 以上の文字列  X に対して,  X の美しさを  b とすると,  X \oplus \gamma~(\gamma \in \mathcal{A}) の美しさは  X の末尾2文字を  \alpha, \beta としたとき,

 b+S_{\alpha \beta \gamma}+S_{\beta \gamma}+S_{\gamma}

である.

また, 長さが  2 の文字列  \alpha \beta~(\alpha, \beta \in \mathcal{A}) の美しさは  S_{\alpha \beta}+S_{\alpha}+S_{\beta} である.

これらのことから, 次の解法が正当性を持つということもわかる.

  • 重み付き有向グラフ  D=(V,A,C: A \to \mathbb{R}) を以下で設定する.
    •  V:=\{{\rm start}, {\rm goal} \} \cup \{\alpha \beta \mid \alpha, \beta \in \mathcal{A} \}
    •  A:=\left \{\overrightarrow{{\rm start}~\alpha \beta} \mid \alpha, \beta \in \mathcal{A} \right \} \cup \left \{\overrightarrow{\alpha \beta~\beta \gamma} \mid \alpha, \beta, \gamma \in \mathcal{A} \right \} \cup \left \{\overrightarrow{\alpha \beta~{\rm goal}} \mid \alpha, \beta \in \mathcal{A} \right \}
    •  C を以下で定める.
 C \left(\overrightarrow{UV} \right)=\begin{cases}
S_{\alpha \beta}+S_{\alpha}+S_{\beta} & (U={\rm start}, V=\alpha \beta) \\
S_{\alpha \beta \gamma}+S_{\beta \gamma}+S_{\gamma} & (\alpha, \beta, \gamma \in \mathcal{A}) \\
0 & (U=\alpha \beta, V={\rm goal})
\end{cases}

このとき, 長さ  2 以上の文字列における美しさの最大値は  D における  {\rm start} を始点,  {\rm goal} を終点とする最大重み walk の重みである.

これを求めるために,  C の値域としては正と負両方があり得るので Dijskra 法を使うことはできない. そこで別の方法を用いることにする. 今回,  D において頂点数は  (|\mathcal{A}|^2+2), 辺の数は約  \left|\mathcal{A} \right|^3 個であるから, Bellman-Ford 法を利用することにより, 重みが正の閉路の検出もでき, それが存在しない場合の最大重み walk の重みも  O(|\mathcal{A}|^5) 時間で求めることができる.

長さ  1 と長さ  2 以上の結果を合わせることによって最終解答を導くことができる. 時間計算量は  O(N+|\mathcal{A}|^5) 時間である.