ABC 215 E — Chain Contestant

考察

選んだ文字を同じ種類ごとに一かたまりにするには、一度離れた種類へ戻らなければよい。左から文字を選ぶとき、「既に使った種類」と「今続けている種類」が分かれば、この条件を判定できる。入力は長くても種類数は10しかないので、この二つの情報へ履歴をまとめて数えられる。

何を一通りとして数えるのか

与えられた文字列から、位置の順序を保って一文字以上を選ぶ。同じ文字は、選んだ列の中で連続する一つのかたまりにならなければならない。AABB はよいが、ABA は A へ戻るので不適切である。元の列で隣接する位置を選ぶ必要はない。

また、数えるのは出来上がった文字列の種類数ではなく、選ぶ位置の集合である。例えば AA には、一文字目だけ、二文字目だけ、両方、という三通りの非空選択がある。この区別は、後で同じ状態の個数を足す理由になる。

長さは最大1000なので、各位置の選ぶ/選ばないをそのまま試す 2N2^N 通りの全探索はできない。そこで左から処理し、今後に同じ影響を与える履歴をまとめたい。

次の文字を選べるか、という問いから状態を作る

今までに AAB を選んでいたとする。次が B なら現在のかたまりを伸ばせる。C なら初めての種類へ移れる。一方 A を選ぶと、終了したかたまりへ戻ってしまう。

この例から、次の文字を選ぶ条件は二つだと分かる。

  • 最後に選んだ文字と同じである。
  • 今まで一度も選んでいない文字である。

どちらか一方の情報だけでは足りない。使用集合が同じ AB と BA でも、次の A は前者へ追加できず後者へ追加できる。逆に、末尾が同じ AB と CB でも、次の A は前者へ追加できず後者へ追加できる。

では、使用集合と末尾を両方残せば十分だろうか。この二つが同じなら、どの次文字を追加できるかが一致し、追加後の使用集合と末尾も同じになる。選ばずに飛ばす場合も変化しない。従って一文字先だけでなく、その後のどんな続きに対しても同じ規則で処理できる。AB、AAB、ABB のような異なる過去を、同じ状態へまとめてよい。

使用集合を10ビットで表し、位置ごとに個数を進める

A〜J を整数0〜9に対応させ、種類数を K=10K=10 とする。集合をビットマスク MM で表し、種類 xx を使ったかどうかを xx ビット目で記録する。集合は 2K2^K 通り、末尾は KK 通りなので、位置を一つ固定した状態数は高々 K2K=10240K2^K=10240 である。

dpi[M][ℓ]dp_i[M][\ell] を、先頭 ii 文字の中から、使用集合が MM、末尾が ℓ\ell となる適切な非空選択の個数とする。まだ何も処理していない dp0dp_0 はすべて0でよい。空の選択はこの表に入れず、「今初めて選ぶ」場合を別に足す。

次に読む文字を xx とする。次の配列を0で用意し、各状態の個数 v=dpi[M][ℓ]v=dp_i[M][\ell] を次のように配る。添字 ii は処理済み文字数で、今回は i+1i+1 文字目を読む。

今回の選択条件次の状態と加算
選ばない常に可能(M,ℓ)(M,\ell) に vv
今のかたまりを延長x=ℓx=\ell(M,ℓ)(M,\ell) に vv
新しい種類を開始x∉Mx\notin M(M∪{x},x)(M\cup\{x\},x) に vv

さらに、今回の位置だけを最初に選ぶ一通りを ({x},x)(\{x\},x) へ加える。使用済みで末尾と異なる種類は、選ぶ遷移を作らない。すべての加算は998244353で割った余りで行う。

x=ℓx=\ell のとき、選ばない場合と選ぶ場合は同じ状態へ入る。しかし選んだ位置集合が異なるため、両方の個数を加える。状態が同じことは、選び方を一つへ消してよいことを意味しない。

ABA で、同じ状態への合流を追う

三つの位置を1、2、3と呼ぶ。先頭二文字 AB を読んだ時点では、次の三状態が一通りずつある。

使用集合末尾選んだ位置
{A}\{A\}A{1}\{1\}
{B}\{B\}B{2}\{2\}
{A,B}\{A,B\}B{1,2}\{1,2\}

最後の A を読むと、最初の状態からは「飛ばして {1}\{1\}」と「選んで {1,3}\{1,3\}」が生まれ、さらに今回から始める {3}\{3\} が合流する。使用集合 {A}\{A\}・末尾 A の個数は3になる。

末尾 B の一文字選択 {2}\{2\} からは BA を作れるが、既に AB を選んだ {1,2}\{1,2\} からは A に戻れない。最終的な個数は、A だけの状態に3、B だけに1、AB に1、BA に1の合計6である。非空の全7選択のうち、不適切なのは三位置をすべて選ぶ場合だけなので一致する。

全 NN 文字を処理した後、すべての状態の個数を足せば答えになる。実装では前の位置の配列だけを読むので、位置方向は現在と次の二配列でよい。

典型の発動条件

状態は、未来の区別に必要な情報から決める

DPの状態を作るときは、まず「同じ状態へまとめようとした二つの過去に、同じ続きを与えて違いが出るか」を試す。本問の AB と BA は、使用集合だけという案が足りないことを示す反例である。

情報を増やした後は、十分性も確かめる。残した情報から次の操作の合法性、次状態、追加される値がすべて決まれば、それ以前の細部は忘れられる。この二段階の確認は、桁DPや経路DP、文字列の有限状態化でも使う。状態を増やすことと、未来に関係しない情報を削ることを往復して設計する。

小さいのが入力長ではなく、種類数でもよい

集合を記録するなら、指数になるのが何かを調べる。本問で 2N2^N は無理でも、使用済み種類の集合は 2102^{10} 通りである。種類ごとの履歴が「使用済みか」の二値で十分で、種類数が小さいときにビットマスクが役立つ。

ただし、種類ごとの使用回数に制限が付けば二値では足りない。また、集合だけで将来が決まらなければ、本問の末尾のような補助情報を組み合わせる。ビットDPという名前から状態を決めるのではなく、まず必要な情報を特定し、その表現と個数を考える。

同じ状態へ来た履歴を、目的に合う値へ集約する

状態は今後の選択を区別するための情報で、その状態に入る値は過去の候補を集約したものである。数え上げなら個数を足し、最小化なら最良値を取り、存在判定なら真偽を取る。本問では同じ部分列が出来上がっても選んだ位置が違えば別候補なので、個数を足して合流させる。

問題固有の要素

「同じ種類が一かたまり」という条件は、同じ文字の繰り返し自体を禁止していない。禁止されるのは、一度別の種類へ移った後の再登場である。選んだ列をかたまり単位に圧縮すると、同じ種類が二回現れない、と言い換えられる。この見方から「使用済み集合」と「現在の種類」の役割を分離できる。

正当性

使用集合と末尾に基づく遷移は、現在のかたまりの延長か、未使用の種類の開始だけを許すので、終了した種類の再登場を作らない。飛ばす操作も適切性を保ち、開始の一文字も必ず適切である。

任意の適切な非空選択を固定する。最初に選んだ位置の開始遷移と、以降の各位置で選ぶか飛ばすかが一意に定まる。適切な選択であれば、文字を選ぶ際は必ず延長か未使用種類の開始なので、DPはその選択を生成する。逆に、一つの遷移列から選ぶ位置集合が一つ決まる。

従って適切な選択とDPで数える選択列は一対一に対応する。同じ状態へ来る個数を加算することで位置による区別も保持し、最終状態の総和は求める個数になる。

実装上の注意

  • 更新前の配列からだけ読む。一文字の処理中に新しい値を読み直すと、同じ位置を複数回選びかねない。二配列にするとこの問題を避けられる。
  • 次配列は毎回0へ戻し、飛ばす分も明示的に加える。コピーして飛ばす分を入れる実装なら、それを重ねて加えない。
  • 集合に含まれる末尾だけが有効な状態になる。初期表はすべて0、各位置からの一文字開始を一回だけ加える。
  • AA の答え3、ABA の答え6、長さ1の答え1を確認すると、同状態への二重の遷移と非空条件を点検できる。

復習の核

  • 「かたまり」は、現在の種類は続けられ、終了した種類へは戻れないという規則に直す。
  • 状態候補には同じ続きを与え、違いの出る履歴を探す。反例がなくなった後は、遷移が決まる理由を示す。
  • 入力長が大きくても、履歴を表す種類数が小さくないか確認する。
  • 同じ状態・同じ出来上がりでも、数える単位が位置集合なら個数を合流させる。

計算量と制約

時間

各文字で高々 K2KK2^K 状態を見て、各状態から定数個の更新を行う。二配列の初期化と最後の総和も含め、O(NK2K)O(NK2^K) 時間である。

空間

DPを現在と次の二層にすると O(K2K)O(K2^K)。入力文字列も保存する場合、全空間は O(N+K2K)O(N+K2^K) である。

制約との対応

1≤N≤10001\leq N\leq1000、文字は A〜J の10種類。最大で約1024万状態を処理すればよく、位置集合の全探索を回避できる。個数は非常に大きくなるが、求めるのは998244353で割った余りなので、各加算のたびに剰余を取る。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Chain Contestant の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: DPの最小十分状態

    補助タグ: 部分集合・bitmask状態DP

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

    学習の位置

    体系上の位置: 最小十分状態からDPを設計する

    • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

    先に読む単元:

    • 部分集合・bitmask状態DP — DPの最小十分状態で得た考え方と実装を再利用し、部分集合・bitmask状態DPの発動条件・正当化・境界を重複なく学ぶ。

    この解説で扱わないこと:

    • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題