AtCoder Beginner Contest 399 E,F問題メモ

AtCoder Beginner Contest 399

E - Replace

• 正整数 $N$ および、英小文字からなる長さ $N$ の文字列 $S,T$ が与えられます。
• 以下の操作を繰り返し（$0$ 回でも良い）行うことで、$S$ を $T$ と一致させることが可能かどうか判定してください。
  • 英小文字 $x,y$ を選び、$S$ に含まれる 全て の $x$ をそれぞれ $y$ で置き換える。
• 可能な場合は、そのために必要な操作回数の最小値も求めてください。

• $1\leq N \leq 2\times 10^5$
• $N$ は整数
• $S,T$ はそれぞれ英小文字からなる長さ $N$ の文字列

意外と条件の洗い出しが難しく、Fより正答者が少なかった。

まず、$S$ の各アルファベットを最終的に何に変化させたら良いか、を整理する。
この時、同じ文字から異なる文字に変化しているような $(S_i,T_i)$ があるとダメ。

S: a a a      ×Sの同じ文字が
T: b b c        Tの違う文字になってたらダメ

S: a b c a d  ○Sの同じ文字はTの同じ文字に変化している。
T: b c a b b    a→b, b→c, c→a, d→b

そしたら、アルファベットの各文字を頂点とし、変化前→変化先で辺を張ったグラフを考える。
これは、各頂点から高々1本の辺が出ているグラフとなる。

各頂点から“ちょうど1本”の辺が出ているグラフは「Functional Graph」といい、いろいろ便利な性質がある。
今回のグラフも Functional Graph にして考えやすくするため、「流入辺のみがあり流出辺が無い頂点は、自己ループの辺が流出辺としてある」ものとする。 「$T$ にのみ存在する文字」がそれに該当し、自己ループは「初期状態から変えなくていい」ことを意味するため、こうしても特に操作回数に影響はない。

また、「$S$ にも $T$ にも存在しない文字」はいったん除いて考える。

a→b→c   d→e→f┐   g┐   h→j→k→l→m←n←o
^-----'         ^┘   ^┘   i↗   ^-----'

Functional Graph の各連結成分は必ず1つのサイクル（自己ループ含む）を持つ。
これを、以下のように4つに分類する。

• ①1文字のみの連結成分（上記 g）
• ②2文字以上で、全ての頂点がサイクル上（サイクルへの流入辺が無い。上記 abc）
• ③2文字以上で、サイクルに流入する辺がある。サイクルは自己ループ（上記def）
• ④2文字以上で、サイクルに流入する辺がある。サイクルは2文字以上（上記h～o）

①は言わずもがな操作の必要は無い。

②は、全てを目標の状態にするにはいったん別の文字を介する必要がある。
たとえば c をいったん z にしておいて、b→c, a→b にしてから、z→a にするなど。
よって、辺の数+1 回の操作が必要となる。

③は、サイクルに近い方から順に揃えていけばよい。自己ループの部分は変える必要は無いので、辺の数-1 回の操作が必要となる。

④は、「②のように辺の数+1 回かな？」と思いきや、実は「辺の数 だけの操作で可能」。
たとえば m を変化させる操作からおこなうとする。目標は k だが、今 k の文字と混ざるとダメなので、いったん1個手前の j にしておく。 すると、のちのちそれを k にする操作ははじめから j だった文字とまとめておこなえる。別の文字を介する必要は無い。

連結成分毎にこれを数えればよい。

ただし、例外がある。
全てが①②のみから構成され、②が1個以上あり、アルファベット26文字全てを使っている場合は、②で「別の文字」を介せないので、不可能となる。

③④があると、そこから手を付けることで文字が「空く」ので、②があっても可能となる。

Python3

F - Range Power Sum

• 正整数 $N,K$ および長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
• $\displaystyle \sum_{1\leq l\leq r\leq N} \Bigg(\sum_{l\leq i\leq r} A_i\Bigg)^K$ の値を $998244353$ で割った余りを求めてください。

• $1\leq N \leq 2\times 10^5$
• $1\leq K \leq 10$
• $0\leq A_i \lt 998244353$
• 入力は全て整数

$(A_1,A_2,...,A_{i-1})$ の結果と $A_{i}$ を使って $(A_1,A_2,...,A_i)$ の結果を求められないか？を考える。

$A_{i}$ を加えることで新たにできる区間は、（当然）$A_i$ を末尾に持つ各区間となる。

K=3
i:  1  2  3  4    i=4 を加えた時を考える
A:  3  1  4  2

         (0) 2
          4  2
       1  4  2
    3  1  4  2
  └---v---┘
  ここの、各行のK乗の和 4^3 + (1+4)^3 + (3+1+4)^3 を X として、既知としておく。
  
  └---v------┘
  ここの、各行のK乗の和 2^3 + (4+2)^3 + (1+4+2)^3 + (3+1+4+2)^3 を求めたい。
  この分だけ、i=3 の時から答えが増加する。

各行の、$A_i$ 追加前の和 ($1+4,3+1+4$ など) を $x,y,...$ とおいて、各行に $A_i$ を追加した後を考える。

   (x+Ai)^3  =  x^3  +     3 * x^2 * Ai    +    3 * x * Ai^2       +  Ai^3
   (y+Ai)^3  =  y^3  +     3 * y^2 * Ai    +    3 * y * Ai^2       +  Ai^3
+ ...
-----------------------------------------------------------------------
 求めたい値  =   X   + 3*(K=2の場合のX)*Ai + 3*(K=1の場合のX)*Ai^2 + (Ai^3 * 行数)

なので、$1,2,...,K-1$ 乗における $X$ に相当する値もわかれば、計算で求められることがわかる。
このとき、各項の係数は二項係数となる。

$X$ を以下のように定義しなおして、

• $X_{k,i}:=A_i$ を末尾とした全ての区間における、$区間和^k$ の総和

$k$ の小さい方、同じ $k$ の中で $i$ の小さい方から $X_{k,i}$ を求めていけば、$X_{K,*}$ の総和が答えとなる。

$O(NK^2)$ で求められる。

Python3