ABC 301 F — Anti-DDoS

考察

禁止部分列は「同じ大文字が2回、その後に小文字、その後に大文字」が揃った時点で完成する。未重複段階では具体的な大文字集合を持たず、種類数 y だけを持てばよい。状態は A_y (0≤y≤26)(重複前)、B(重複後でまだ小文字なし)、C(重複後に小文字あり、後続大文字なし)の計29個。

? から A_y は26通りの小文字でA_y、y通りの既出大文字でB、26−y通りの新大文字でA_{y+1}へ進む。Bは大文字26通りでB、小文字26通りでC。Cは小文字26通りでC、大文字は全て禁止完成として捨てる。固定小文字はA_yとCに留まり、BからはCへ進む。固定大文字はBではBへ、Cでは禁止完成として除き、A_yからは次の割合で分ける。

固定大文字を読むときは、固定prefixに既出の大文字種類数をxとして持つ。既出固定文字ならA_yから必ずBへ進む。新しい固定文字なら、A_yのうち割合 (y−x)/(26−x) が既にその文字を?で使っておりBへ、残り (26−y)/(26−x) が未使用でA_{y+1}へ進む。遷移後にxを一つ増やす。

採用する候補: 文字集合の対称性で種類数へ圧縮した29状態DP

?由来の大文字は固定文字以外で対称なので、既出種類数だけで遷移係数を決められる。

棄却する候補: 既出大文字集合2^26をそのまま状態にする。

文字列長3×10^5に対して状態が大きすぎる。

初期値は A_0=1、他のDP状態0、x=0。全文字を処理した後の Σ_{y=0}^{26}A_y+B+C が答えである。禁止が完成する遷移だけを捨てているので、残る全状態を集計する。

典型の発動条件

automaton DP

発動条件: 禁止/要求subsequenceの進行が有限状態で表せる。

文字列prefixごとに最長進行段階を更新する。

対称性による集合圧縮

発動条件: 26文字集合の種類名でなくcardinalityだけが遷移確率に効く。

既出大文字数yを状態にする。

問題固有の要素

固定大文字と?由来大文字を分け、具体名の対称性を種類数へ圧縮することで2^26を29状態に落とす。

別の問題へ持ち帰る視点: alphabet対称性がある集合状態はサイズ統計へ縮約する。

正当性

A_y では固定prefixに含まれるx種類以外の26−x文字が対称であり、そのうちy−x種類を既に?で選んでいる。したがって新しい固定大文字が既出集合に含まれる割合は (y−x)/(26−x) で、残りは新種類として加わる。? の52文字は状態定義どおり小文字、既出大文字、新大文字へ漏れなく分かれる。固定小文字はA_y,Cを保ちBをCへ進め、固定大文字はA_yを上記の割合で分け、Bを保ち、Cからの遷移を禁止完成として除く。これらは部分列が完成する瞬間をちょうど除外するので、DPは全ての未禁止prefixを一度ずつ数える。

実装上の注意

  • 状態は A_0,…,A_26,B,C の29個。固定prefixの大文字種類数xは、固定大文字を読むたび、重複判定より後で更新する。
  • 固定大文字の係数はmod上で分数として計算し、26−x は新しい固定文字がある間だけ分母にする。?は小文字26通り・大文字26通りで数える。

復習の核

  • 短文字列の52^q全探索と比較し、同大文字2回、重複間/後の小文字、?だけの例を確認する。

計算量と制約

時間

O(29|S|)。固定prefix大文字種類と定数状態DP。

空間

O(29+26)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: S consists of uppercase English letters, lowercase English letters, and ?.; The length of S is between 4 and 3\times 10^5, inclusive.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Anti-DDoS の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 有限状態automatonの構成

主題
  • 有限状態automatonの構成: 未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。
追加で学ぶ技能
  • automaton上のDP・行列遷移: 位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
既習技能

主タグ: automaton上のDP・行列遷移 有限状態automatonの構成

補助タグ: 法上の四則演算・高速累乗・逆元 状態・配置の正規化

執筆: abc-explanation-author1.1.1 / revision 2

学習の位置

体系上の位置: 有限状態automatonの構成

  • 未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。
  • 位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

先に読む単元:

学習記録

状況更新: 更新記録なし

復習設定更新: 更新記録なし

端末内の保存状態を確認しています。

要復習一覧 / 学習記録のバックアップ / 解説に戻る

同じ単元の問題