ABC 418 G — Binary Operation

考察

隣接二文字の縮約は、文字順を保った二分括弧付けに対応する。短い文字列は、区間を全分割し左右の到達値を演算する区間DPで判定できる。しかし全substringへこのDPを行うと間に合わない。

各演算の「1へ縮約できる非空文字列」を有限オートマトンで表す。短い継続suffixを付けたときの受理結果をsignatureとし、同じsignatureのprefixをまとめてDFA候補を作る。長さ3以下の全suffixを使い、空prefixからBFSで0/1を追加すると、以下の表を得る。ABCDはf(0,0),f(0,1),f(1,0),f(1,1)の順。状態0が初期状態で、受理1はbeautifulを意味する。

ABCD各状態の (0遷移,1遷移,受理)
00000:(1,2,0); 1:(1,1,0); 2:(1,1,1)
10000:(1,2,0); 1:(3,4,0); 2:(5,5,1); 3:(4,6,1); 4:(6,6,0); 5:(6,4,0); 6:(6,6,1)
01000:(0,1,0); 1:(2,2,1); 2:(2,3,0); 3:(2,3,1)
11000:(1,2,0); 1:(3,3,0); 2:(1,1,1); 3:(3,3,1)
00100:(1,2,0); 1:(1,1,0); 2:(3,4,1); 3:(3,3,1); 4:(4,3,0)
10100:(1,2,0); 1:(3,4,0); 2:(3,4,1); 3:(3,3,1); 4:(3,3,0)
01100:(0,1,0); 1:(1,0,1)
11100:(1,2,0); 1:(3,3,0); 2:(4,1,1); 3:(3,3,1); 4:(3,1,1)
00010:(1,2,0); 1:(1,1,0); 2:(1,2,1)
10010:(1,2,0); 1:(2,1,0); 2:(1,2,1)
01010:(0,1,0); 1:(0,1,1)
11010:(1,2,0); 1:(3,3,0); 2:(1,2,1); 3:(3,3,1)
00110:(1,2,0); 1:(1,1,0); 2:(2,2,1)
10110:(1,2,0); 1:(2,1,0); 2:(2,2,1)
01110:(0,1,0); 1:(1,1,1)
11110:(1,2,0); 1:(2,2,0); 2:(2,2,1)

ただし短い語の一致や二段の安定だけでは、一般の言語について正しさは証明できない。この表は次の有限な検査で、全ての長さに対して証明できる。L_bを値bへ縮約できる非空文字列の言語とすると、

L_b={b} ∪ ⋃_{f(a,c)=b} L_a L_c

である。0へ縮約する候補DFAは、演算f'(a,c)=1−f(1−a,1−c)の表を取り、入力文字0/1を交換すれば得られる。この二つの候補言語に対して右辺の連接・和集合をNFAで構成し、左辺のDFAとの積オートマトンをBFSする。片方だけ受理する到達状態がなければ言語が厳密に一致する。表の16演算×2値について、この有限検査は全498個の到達積状態で成功する。これで語長に上限を置かず表を確定できる。

各演算のDFAで入力Tを左から走査する。cnt[q]は直前位置で終わるsubstringが状態qへ到達する個数、start[q]はその中の最小開始位置。次文字cへcnt'[δ(q,c)]+=cnt[q]、start'へ最小を伝播し、状態δ(0,c)へ新しい長さ1のsubstringを一つ加える。受理状態のcntの総和をMへ足し、最小startから最大長Lを更新する。表は高々7状態なので各演算O(N)。

典型の発動条件

Myhill-Nerode同値類

発動条件: 文字列languageのprefixを、将来suffixに対する受理挙動だけで有限状態化するとき。

bounded suffix signatureを精密化し、安定したclassをDFA stateにする。

DFA上の全substring DP

発動条件: 固定文字列の全substringについてregular language受理数と最長長を求めるとき。

ending位置ごとに全stateのcountと最早startを一文字遷移する。

interval parsing DP

発動条件: 短いwordを二項演算で任意順に縮約した到達値を判定するとき。

区間分割と左右到達bitの組から区間の可能値集合を求める。

問題固有の要素

16個の二項演算に限定された小さな言語を、継続signatureで推測し、文法方程式との厳密な有限比較で確定する。未知の文脈自由言語が短い実験だけで正規と分かるわけではない。

別の問題へ持ち帰る視点: 小さな演算の全ケースでは、実験で候補を作り、再帰的な言語の定義と照合して証明する手順が有効である。確定したDFAでは全substringの個数・最長長を同じ状態遷移で集計できる。

正当性

表の候補言語が二つの文法方程式と一致することは、連接NFAとDFAの積で全ての到達状態を検査して確認できる。両候補は空文字列を受理せず、連接の両因子は真に短い。長さ1は{b}の基底、長さ2以上は最終縮約の左右分割で決まるため、語長についての帰納法により、この方程式を満たす候補は実際の全括弧付けの言語と一致する。短い語の実験だけを一般的なDFA学習の停止保証にしていない。

DFAの同じ状態へ到達するsubstringは、次の全ての文字列に対して同じ受理挙動になるので、個数と最小開始位置へ集約できる。各位置で既存のsubstringを一文字伸ばし、新規の長さ1を一つ開始することで、全非空substringを一度だけ数える。受理状態の個数がM、最早開始位置がその右端での最長受理substringを与える。

実装上の注意

  • beautifulは非空なのでempty start stateの受理をsubstring集計へ混ぜない。演算indexは00=A,01=B,10=C,11=D、MはO(N^2)なので64 bit、受理なしならL=-1とする。

復習の核

短い語による候補推測と、文法方程式の有限比較による確定を分ける。連接NFAは左側が受理する各位置で右側の開始状態へε遷移し、全ての分割位置を表す。

計算量と制約

時間

O(16sN+C)、s≤7。Cは固定された16演算の表構築・文法方程式照合の定数費用。各substring scanでは状態ごとに一遷移。

空間

O(s)。各演算のscanでは個数と最小開始位置の二layerのみ。表構築と照合も入力Nに依存しない定数空間。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; N is an integer.; T is a string of length N consisting of 0 and 1.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Binary Operation の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

補助タグ: DPの最小十分状態 区間合成・領域分割DP

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

学習の位置

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

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

先に読む単元:

  • 区間合成・領域分割DP — DPの最小十分状態で得た考え方と実装を再利用し、区間合成・領域分割DPの発動条件・正当化・境界を重複なく学ぶ。
  • 最小十分状態からDPを設計する — 初歩的な一次元DPを土台に、未来を決める情報だけを残す最小十分状態の設計原則を学ぶ。

学習記録

状況更新: 更新記録なし

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

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

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

同じ単元の問題