むかでのチラ裏

競技プログラミング現役引退でチラ裏に・・・

Educational Codeforces Round #107 (Div.2) D - Min Cost String

ECR 構築 オイラー路

この問題かなり難しく感じました． よく観察すると典型に落とし込めるということで，記事にしました．

問題概要

文字列 $ S = S_1S_2 \cdots S_{|S|} $ のコストを次のように定義する．

  • $ 1 \leq i < j \leq |S| $ のようなペア $ (i,j) $ であって， $ S_i = S_j $ かつ $ S _ {i+1}=S _ {j+1} $ であるようなものの数

英小文字の最初の $ K $ 文字のみで構成される長さ $ N $ の文字列でコストが最小のものを $ 1 $ つ出力せよ．

制約

  • $ 1 \leq N \leq 2 \times 10^{5} $
  • $ 1 \leq K \leq 26 $

考察

まず，長さ $ N $ 文字列には $ 2 $ 文字の連続する部分文字列が（重複を含めて） $ N-1 $ 個ある． 文字列のコストはこの $ N-1 $ 個の部分列の等しいものの組み合わせの総和と等しい． よってコストを $ cost $ ，連続する部分文字列 $ ij $ の数を $ cnt_{i,j} $ として，次の式が成り立つ．

\begin{align} cost &= \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} \frac {(cnt _ {i,j})(cnt _ {i,j}-1)}{2} \\ &= \frac{1}{2} \left\{ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} (cnt _ {i,j})^{2} - \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} cnt _ {i,j} \right\} \\ &= \frac{1}{2} \left\{ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} (cnt _ {i,j})^{2} - (N-1) \right\} \hspace{15pt} \left(\because \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} cnt _ {i,j} = N-1\right) \end{align}

上の式で変数は $ cnt_{i,j} $ のみであるから，$ cost $ を最小化するには $ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} (cnt _ {i,j})^{2} $ を最小化すればよいことがわかる．

$ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} cnt _ {i,j} = N-1 $ であるから，和が一定の数列の二乗和を最小化すればよいことが分かり，これは（できるだけ）等しくなるように分配すれば良い（証明略）．

※実数の場合はコーシー・シュワルツの不等式で簡単に証明できる．

したがって，なるべく $ 2 $ 文字の連続部分文字列が被らないように文字列を構築していくことを考えればよい．この連続部分文字列は $ K^{2} $ 種類存在する．そして実は $ K^{2} $ 種類の $ 2 $ 文字連続部分文字列を全て含む 長さ $ K^{2}+1 $ の文字列を構成することが可能である．

ここでアルファベットを頂点に対応させたグラフを考える． すると $ 2 $ 文字の連続部分文字列は辺に対応し，文字列はこのグラフ上の歩道に対応する．

f:id:spider_0859:20210413193856p:plain:w250
K=4 の時のグラフ

任意の辺を 1 回ずつ通る歩道をグルグル回れば，連続部分文字列の分布を最もフラットにできる． このような歩道は，オイラー路（Eulerian trail）の定義そのものである．

オイラー路を持つためには，すべての頂点の入次数と出次数が等しくなければならない． このグラフは，すべての頂点間に 1 本ずつ有効辺が伸びているため明らかに条件を満たしている． オイラー路の構築はグラフのサイズを $ M $ として， DFS で $ O(M) $ で構築が可能である（隣接行列のためのメモリの確保は別に考えています）．

オイラー路に対応する文字列を構築したら，長さ $ N $ に達するまで連結することで答えが得られる． 全体で $ O(N+K^{2}) $ で答えを得ることができる．

別解（コンテスト中の解法）

コンテスト中には全然オイラー路が見えなかったが長さ $ 2 $ の連続部分文字列 $ K^{2} $ 種類が被らない文字列を規則的に構築するための観察をしていた．

  • $ K=1 $ の時は自明に "aa"
  • $ K \geq 2 $ の時は $ K - 1 $ の時の文字列に $ K $ 番目のアルファベットを含む $ 2 $ 文字の文字列を含むようにすれば良い．
    • $ K=2 $ の時 "bb"+"aa"+"b"
    • $ K=3 $ の時 "cc"+"bbaab"+"cac"

上記のように再帰的に構築可能である．

個人的ポイント

  • 要素を頂点，ペアを辺に対応させてグラフの問題に落とすことは多々ある．
  • オイラー路は $ O(M) $ で構成可能．
    • 厳密には隣接行列を連想配列でするなどにより log が付いたりしそう．
  • $ 1 $ パラメータの構築は，$ 1 $ つ前のものから簡単な手続きで作れることが多い．
    • 再帰的な構築を考える．

参考資料

競プロにおけるオイラー路とその応用について - Learning Algorithms

  • これを見てオイラー路を構成を勉強しました．

ソースコード

オイラー路解

再帰構築解

▶ソースコードを展開