ABC 299 F — Square Subsequence

考察

同じ文字列を何通りの位置から取り出せても、答えには一度だけ数える。そこで、二コピーをつなげた全体を「各文字をできるだけ左から取る」という規則で一意に表す。後半の先頭位置を仮に固定して二コピーを同時に伸ばし、全体の規則に合うものだけを答えに加える。

求めるのは、非空な文字列 TT のうち、二つ連結した TTTT が入力文字列 SS の部分列となるものの種類数である。N=∣S∣N=|S| とする。位置を選ぶ全探索は 2N2^N 通りある上に、その選び方の個数は答えと異なる。例えば S=aaa から aa を取る位置は (1,2),(1,3),(2,3)(1,2),(1,3),(2,3) の3通りだが、対応する T=a の寄与は1である。

一つの文字列を左から順に作るとき、次の文字は直前に選んだ位置より右にある同じ文字のうち、最も左のものから取ればよい。早く取るほど後ろに使える部分が広く残るため、取り出せる文字列をこの規則で取り逃すことはない。こうして各文字列に一つの取り出し方を対応させる。

位置は1始まりとし、σ(i,c)\sigma(i,c) を「位置 ii より厳密に右で文字 cc が最初に現れる位置」と定義する。存在しなければ番兵 N+1N+1 を返す。i=0i=0 は文字列の先頭より前を表す。0≤i≤N0\leq i\leq N と英小文字26種類について表を用意する。行 NN をすべて N+1N+1 とし、右から左へ、行 ii を行 i+1i+1 のコピーで作った後に σ(i,Si+1)=i+1\sigma(i,S_{i+1})=i+1 とすれば、O(26N)O(26N) 時間で前計算できる。

二コピーを全体として最左から取るには、後半の先頭を、前半の末尾の直後から探す必要がある。しかし、前半の末尾は TT を作り終えるまで分からない。そこで後半の先頭位置 xx を先に固定し、前半・後半の各コピーをそれぞれ最左から伸ばす。前半の現在の末尾を pp とすると、p<xp<x を保てば二コピーは順番どおりに並ぶ。ただし、これだけで重複は消えるだろうか。

先ほどの S=aaa, T=a をこの方針で取り出すと、前半先頭は位置1、後半先頭 xx は2または3となる。両方とも p<xp<x を満たし、各コピーの中では最左から取っているが、全体 TT=aa の最左の取り出し方は (1,2)(1,2) だけだ。

二コピーの位置前半末尾から次の a を探す
(1,2)(1,2)σ(1,a)=2=x\sigma(1,\mathrm{a})=2=x なので数える。
(1,3)(1,3)σ(1,a)=2≠x\sigma(1,\mathrm{a})=2\ne x なので数えない。

つまり、各コピーの内部を最左化することに加えて、コピー間のつなぎ目も最左であると確かめる必要がある。後半の先頭文字は SxS_x なので、現在の文字列を完成した TT として数える条件は

σ(p,Sx)=x\sigma(p,S_x)=x

となる。この条件が、仮に選んだ xx と、TTTT 全体を最左から取ったときの後半先頭を一致させる。

具体的には、x=1,…,Nx=1,\ldots,N を一つずつ固定して次のDPを行う。TT の先頭文字は SxS_x と決まるため、前半先頭を p1=σ(0,Sx)p_1=\sigma(0,S_x) とする。p1≥xp_1\geq x ならこの xx は使えない。それ以外は dp[p1][x]=1dp[p_1][x]=1、その他を0として始める。最初から1文字選んでいるので、空の TT は含まれない。

dp[p][q]dp[p][q] は、ここまでに作った同じ非空文字列を前半では SS の先頭から、後半では固定した位置 xx から、それぞれ最左の出現へ進んで取り出したとき、末尾が p,qp,q となる文字列の種類数とする。有効な添字は 1≤p<x≤q≤N1\leq p<x\leq q\leq N である。次に同じ文字を付け足せるかどうかは、この末尾の対と xx だけで決まるため、異なる文字列が同じ状態に集まったら個数を足してよい。

次の1文字 cc を26種類から選び、

p′=σ(p,c),q′=σ(q,c)p'=\sigma(p,c),\qquad q'=\sigma(q,c)

とする。p′<xp'<x かつ q′≤Nq'\leq N のときだけ、

dp[p′][q′]+=dp[p][q]dp[p'][q']\mathrel{+}=dp[p][q]

と更新する。位置の選び方を分岐させず、追加する文字だけを選ぶ遷移である。両添字は厳密に増えるので、pp を昇順、その内側で qq を昇順に走査すればよい。

各状態では、終了条件 σ(p,Sx)=x\sigma(p,S_x)=x を満たす場合だけ dp[p][q]dp[p][q] を答えへ一度加える。固定した xx からの寄与は

∑σ(p,Sx)=x∑q=xNdp[p][q]\sum_{\sigma(p,S_x)=x}\sum_{q=x}^{N}dp[p][q]

となる。集計後も次文字への遷移は続ける。また、今は終了条件を満たさなくても、延長後に満たす場合があるので状態を捨てない。全ての xx について集計し、加算は法 998244353998244353 上で行う。

例えば S=aaaa では、x=2x=2 の初期状態 (1,2)(1,2) が T=a を数える。x=3x=3 の初期状態 (1,3)(1,3) は数えないが、a を付け足すと (2,4)(2,4) へ進み、σ(2,a)=3=x\sigma(2,\mathrm{a})=3=x なので T=aa を数える。x=4x=4 の初期状態も数えず、延長時は後半の次位置が番兵 5=N+15=N+1 となるため遷移を捨てる。答えは a と aa の2種類である。

集計した状態からの延長も必要で、例えば S=abab の x=3x=3 では、(1,3)(1,3) で T=a を数えた後、b を足した (2,4)(2,4) で T=ab も数える。

典型の発動条件

distinct subsequenceのcanonical embedding

発動条件: 同じ文字列を得る位置の選び方が複数あっても、文字列の種類数を数えたい。

各文字を可能な限り左の出現から取ると、後続の選択を狭めずに代表となる取り出し方を一つに固定できる。複数の部分を組み合わせる場合は、それぞれの内部だけでなく、つなぎ目も代表の規則と一致するかを確認する。

二列同期遷移DP

発動条件: 同じ未知文字列を二つの部分列として同時に作りたい。

二つの末尾位置を状態にし、同じ次文字で両方を進める。次の出現位置を一意に決めれば、DPの値は取り出す位置の選び方の個数ではなく、生成した文字列の種類数を表せる。

問題固有の要素

二つの同じコピーを前後に置くため、後半の先頭位置を固定すると、その文字と前半の先頭位置も決まる。残る全体の最左規則は、前半末尾から後半先頭へ移る一か所だけで検査できる。

別の問題へ持ち帰る視点: 部分ごとに代表を決めても、組み合わせ全体の代表が一意になるとは限らない。境界を固定し、最後に境界をまたぐ規則を確かめる。

正当性

SS に含まれる任意の非空文字列 TTTT を考える。各文字を直前の位置より右の最左の出現から取る方法は、他の取り出し方より各位置が右にならないため、必ず最後まで成功する。この方法は一意であり、後半先頭位置 xx も一意に決まる。前半の全位置は xx より左なので、その文字列は対応する xx のDPで初期化から順に同じ文字を選ぶ遷移をたどれる。前半末尾を pp とすると σ(p,Sx)=x\sigma(p,S_x)=x も満たすため、必ず答えへ加えられる。

逆に、DPで集計した状態は、前半末尾が p<xp<x で、二つのコピーが同じ文字列を表す有効な部分列である。前半の取り出しは先頭からの最左規則に従い、終了条件が後半の先頭でも同じ規則を保証し、後半の残りも最左遷移に従う。従って、その取り出し方は TTTT 全体の一意な最左の取り出し方に一致する。

固定した xx と文字列 TT に対して、選ぶ文字列と各次位置は一意なので、DP内で同じ TT を複数回生成しない。異なる xx で同じ TT を集計することも、全体の最左の取り出し方の一意性に反する。よって各 TT は漏れなく一度だけ数えられる。

実装上の注意

  • σ\sigma は「現在位置より厳密に右」を返す。同じ位置の文字を再利用しない。
  • 次位置が番兵 N+1N+1 の遷移は捨てる。p′<xp'<x と q′≤Nq'\leq N を確認すれば、両方の消失を除ける。
  • 初期化前に p1≥xp_1\geq x の場合を除く。長さ1から始めるため、空の TT は答えへ加わらない。特に N=1N=1 では有効な初期状態がなく、答えは0になる。
  • 終了条件は答えへの集計条件であり、遷移を止める条件ではない。成否にかかわらず延長を試し、各状態は一度だけ集計する。
  • xx ごとにDPを0へ戻し、前の xx の結果を混ぜない。DPと答えへの加算のたびに法 998244353998244353 を取る。

復習の核

  • 「位置の選び方」と「得られる文字列の種類」を区別し、各文字列の代表となる取り出し方を決める。
  • 部分ごとの最左化だけで重複が消えるかは、aaa の (1,2)(1,2) と (1,3)(1,3) で確かめる。境界をまたぐ最左規則も必要である。
  • 短い文字列を数えた状態も、まだ数えられない状態も延長できる。集計条件と遷移条件を分ける。

計算量と制約

時間

次出現表の前計算に O(26N)O(26N) 時間。固定した xx ごとにDPの初期化・走査・集計は O(N2)O(N^2)、各状態から高々26文字の遷移を行うので O(26N2)O(26N^2) 時間となる。xx は高々 NN 通りで、全体は O(26N3)O(26N^3) 時間。

空間

一つの xx のDPが O(N2)O(N^2)、次出現表が O(26N)O(26N)、入力が O(N)O(N)。xx を一つずつ処理して同じDP領域を使い回すため、全体は O(N2+26N)O(N^2+26N) 領域。

制約との対応

1≤N≤1001\leq N\leq 100、文字は英小文字26種類。遷移候補は高々 26×1003=2.6×10726\times100^3=2.6\times10^7 回で、位置の全探索を避けて処理できる。答えは種類数を 998244353998244353 で割った余りとして求める。制限時間は2秒、メモリ制限は1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Square Subsequence の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 列・subsequence DP

主題
  • 列・subsequence DP: 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 列・subsequence DP

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

      学習の位置

      体系上の位置: 列・subsequence DP

      • 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題