ABC 264 G — String Fair

考察

文字列全体を候補にすると、長さに上限がないため探索が終わらない。そこで、一文字を付け足したときの得点だけを調べる。審査される語が長さ3以下なので、増える得点は直前の二文字から決まり、無限個の文字列を有限個の状態へまとめられる。長さの無制限性は、その状態へ何度も戻って得点を増やせるか、という閉路の問題になる。

無限の長さを探す前に、得点の増え方を調べる

英小文字からなる非空文字列を作り、指定された語の出現回数に得点を掛けて足す。語は連続部分文字列として数え、出現が重なってもよい。例えば aaa に aa は二回現れる。得点には負数もあるので、単に長くするほど有利とは限らない。

入力にない語の得点を0とし、語 TT の一出現に対する得点を P(T)P(T) と書く。次の独自例で、一文字追加する前後を比べよう。

審査語ababbaababab
得点−2−143−21

ba に b を追加すると、既存の b、a、ba の出現はそのままである。増えるのは、新しい右端で終わる b、ab、bab の三つだけだ。従って増分は −1+4+1=4-1+4+1=4。ba の得点0にこれを足して、bab の得点4になる。

一般に、末尾が a,ba,b の列へ cc を追加する増分は、

Δ(a,b,c)=P(c)+P(bc)+P(abc)\Delta(a,b,c)=P(c)+P(bc)+P(abc)

である。ここで bc,abcbc,abc は文字をつないだ語を表す。どの出現にも右端が一つあり、その右端を追加した瞬間だけ数えれば、重なる出現も漏れずに扱える。

末尾が同じなら、長い過去を忘れられる

末尾二文字が同じ二つの列に、同じ文字を付けてみる。増分は上の式で一致し、追加後の末尾も一致する。これを繰り返せば、どんな続きに対しても追加得点は等しい。従って、その二つの列は、今までの得点が高い方だけ残せばよい。

末尾一文字では足りない。例の aa と ba はどちらも a で終わるが、b を付けた増分はそれぞれ3と4である。違いは三文字語 bab が完成するかどうかにある。「審査語の最大長が3」という制約から、残すべき長さは2だと分かる。

状態を二文字の組 abab とすると、一文字追加は次の辺になる。

ab→ Δ(a,b,c) bcab\xrightarrow{\ \Delta(a,b,c)\ }bc

辺に、追加した文字と得点増分を持たせる。グラフ上の歩行、すなわち頂点の再訪を許す辺列が、そのまま文字列の生成手順である。

開始直後には二文字が存在しないので、入力に現れない記号 # で左側を埋め、始点を ## とする。# を含む語の得点は0とし、追加するのは英小文字だけにする。すると、最初の二文字でも同じ式が使える。

追加後の列状態今回の増分累計
空列##—0
a#a−2−2
abab−1+4=31
ababa−2+3−2=−10
ababab−1+4+1=44

27種類の記号の二文字組をすべて用意すれば、頂点数は V=272=729V=27^2=729。各頂点から26本の辺を張るので、辺数は E=26V=18954E=26V=18954 である。例えば a# のような到達不能状態も含むが、始点から到達した状態だけを使えば問題ない。

「長くすれば儲かる」を閉路で捉える

表では、ab から a,b を追加すると再び ab へ戻り、得点は1から4へ増える。同じ二文字を何回でも追加でき、1周ごとに3点増えるので、この例の答えは Infinity だ。

一つの語に正の点が付いているだけでは、無限大とは限らない。例えば全単文字に−1、ab だけに+1なら、ab の得点は−1、繰り返すほど減点される。調べるべきなのは、ある状態へ戻るまでの増分の合計である。

始点から到達できる正の重みの閉路があれば、そこまで進んだ後、同じ閉路を繰り返せばよい。逆に正閉路がなければ、頂点を再訪する部分を取り除いても得点は下がらない。残るのは高々 V−1V-1 辺の単純な道であり、長さ無制限でも有限の探索で最大値が求まる。

辺数を一つずつ増やし、改善が止まるかを見る

Dk[v]D_k[v] を「始点から高々 kk 辺で頂点 vv に着く最大得点」とする。到達不能は −∞-\infty と表す。初期値は始点だけ0、他は到達不能である。

一段の処理では、まず現在の配列を次の配列へコピーする。その後、各辺 u→vu\to v の重みを ww として、現在の Dk[u]D_k[u] が有限なら、次を更新する。

Dk+1[v]←max⁡(Dk+1[v],Dk[u]+w)D_{k+1}[v]\leftarrow\max(D_{k+1}[v],D_k[u]+w)

読む配列と書く配列を分けると、一段が「辺を高々一本追加する」に一致する。これを VV 段行い、最後の段で一つでも値が増えたら Infinity。増えなければ、DV−1D_{V-1} の始点以外の有限値の最大を返す。途中の一段で更新がなくなった場合も、それ以降は同じなので終了できる。これはBellman–Ford法の緩和を最大化として行う方法である。

非空条件のため、始点の0を答えに混ぜない。# は追加できず、一度始点を離れたら戻れないので、始点以外の到達状態はちょうど非空文字列に対応する。

典型の発動条件

全体の評価を、最後の一操作の増分へ分ける

文字列を作る問題では、完成形を毎回評価する代わりに、「今回初めて数える対象は何か」を探す。出現を右端で分類すれば、同じ出現を二度数えず、過去の得点を確定できる。本問では長さ3以下という局所性によって、まだ未来に関与するのは末尾二文字だけになる。

最大語長が LL、文字種数が σ\sigma なら、短い末尾をそのまま保存する状態数はおよそ σL−1\sigma^{L-1} である。LL が小さい場合の有力な方法だが、長い語には指数的に増える。語が長くても本数が限られるなら、語の接頭辞と一致する末尾だけを残すAho–Corasickなどが候補になる。残す情報は、文字列の長さそのものではなく、未来の得点や判定へ影響する未完了部分で決める。

有限状態を作った後で、長さの条件に合う解法を選ぶ

同じ状態グラフでも、長さを固定するなら位置ごとのDP、長さが巨大で遷移が一定なら行列累乗、長さ無制限の最大化なら正閉路の判定を考える。状態が有限になっただけでは、歩行の長さまで有限になったとは言えない。

正閉路が答えへ影響するには、始点からそこへ到達できることが必要である。本問はどこで終了してもよいので、それだけで十分だ。終点指定の問題なら、閉路から終点へも到達できる必要がある。零閉路は何周しても同じ得点なので、最適な列を無限に多数作れても、最大得点は無限大にならない。

問題固有の要素

核心となる制約は、生成する列が長さ無制限なのに対し、審査語の長さは3以下という非対称性である。前者は反復の可否を、後者は一回の反復を記述する状態数を決める。両方を別々に読むことで、「無限個の候補を有限グラフへ移し、その閉路を調べる」という方針へ到達できる。

また、入力にない文字も生成できる。審査語に現れない文字を勝手に除くと、負の語の出現を避ける区切り文字を失う可能性があるため、全26文字の遷移を作る。

正当性

各審査語の出現を右端の位置へ割り当てると、各出現は一つの遷移の増分にだけ含まれる。開始時の # は得点に寄与せず追加もできないため、始点からの一辺以上の歩行と非空文字列は対応し、辺重みの総和は美しさに等しい。

高々 k+1k+1 辺の歩行は、高々 kk 辺の歩行、または高々 kk 辺の歩行に最後の一辺を付けたものに分けられる。コピーと全辺の緩和はこの二つをすべて扱うので、二層更新は定義どおりの DkD_k を計算する。

到達可能な正閉路がなければ、到達可能な閉じた歩行の重みは0以下である。歩行中の頂点の重複部分を除去しても得点は下がらず、同じ終点へ高々 V−1V-1 辺で到達できる。始点には戻れないので、非空の歩行をこのように縮めても空にはならない。従って各状態の最大値は DV−1D_{V-1} で得られ、VV 段目に改善はない。ゆえに最後の段に改善があれば正閉路が存在する。

逆向きも確認する。到達可能な正閉路があるのに VV 段目で改善しないと仮定する。閉路上の各頂点は単純な道でも到達できるため、DV−1D_{V-1} はすべて有限である。改善がないなら閉路の各辺について、

DV−1[v]≥DV−1[u]+w(u,v)D_{V-1}[v]\geq D_{V-1}[u]+w(u,v)

が成り立つ。閉路に沿って足すと左右の距離が相殺され、閉路重みが0以下になって矛盾する。従って正閉路は必ず検出され、その反復で得点を無限に増やせる。改善がない場合に始点以外の最大値を返す処理も、非空文字列の有限最大値を正しく求める。

実装上の注意

  • 二文字組を整数へ符号化し、各辺の重みを先に計算する。緩和の内側で文字列の生成や辞書探索を繰り返す必要はない。
  • 到達不能からは緩和しない。−∞-\infty の代用値に重みを足す処理も避ける。
  • 各段は旧配列だけを読む。配列内でそのまま更新する実装もBellman–Ford法として可能だが、ここで説明した「高々 kk 辺」という意味とは区別する。
  • 一辺の絶対重みは最大 3×1093\times10^9。VV 段までの値は絶対値 3×109V3\times10^9V 以下なので、重みもDPも符号付き64 bit整数にする。
  • 全26単文字が−1なら答えは−1である。初期値0や、空文字列を最終候補へ混ぜないことをこの境界で確認できる。

復習の核

  • 局所的な出現の総和は、追加した一文字を右端に持つ出現へ分ける。
  • 残す末尾の長さは、次の増分を決めるために何文字必要かから導く。
  • 長さ無制限の最適化では、到達可能な改善閉路と、零閉路を区別する。
  • 状態グラフと開始・終了条件をセットで作る。非空条件を後から忘れない。

計算量と制約

時間

文字種数を σ=26\sigma=26 とし、V=(σ+1)2V=(\sigma+1)^2、E=σVE=\sigma V とする。得点表の初期化・入力は O(σ3+N)O(\sigma^3+N)、全辺の構成は O(E)O(E)。二層Bellman–Ford法は、配列コピーも含め O(V(V+E))=O(VE)O(V(V+E))=O(VE) 時間なので、全体は O(N+σ3+VE)O(N+\sigma^3+VE)。本問のグラフでは最後の項は約1382万辺の緩和に相当する。

空間

長さ1〜3の語の得点表に O(σ3)O(\sigma^3)、辺一覧に O(E)O(E)、二つのDP配列に O(V)O(V) を使い、全体で O(σ3+E+V)O(\sigma^3+E+V)。入力を得点表へ直接格納すれば審査項目の別保存は不要である。

制約との対応

N≤18278N\leq18278、∣Ti∣≤3|T_i|\leq3、∣Pi∣≤109|P_i|\leq10^9。語の短さが729頂点・18954辺への圧縮を可能にする。得点が負にもなるため、正の辺の存在だけで無限大と判定せず、到達可能な正閉路を調べる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

String Fair の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

主題
  • 有限状態automatonの構成: 未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。
追加で学ぶ技能
  • 最短路モデル: 辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。
既習技能
    なし

    主タグ: 有限状態automatonの構成 最短路モデル

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

    学習の位置

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

    • 未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。
    • 辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題