ABC 264 G — String Fair
考察
文字列全体を候補にすると、長さに上限がないため探索が終わらない。そこで、一文字を付け足したときの得点だけを調べる。審査される語が長さ3以下なので、増える得点は直前の二文字から決まり、無限個の文字列を有限個の状態へまとめられる。長さの無制限性は、その状態へ何度も戻って得点を増やせるか、という閉路の問題になる。
無限の長さを探す前に、得点の増え方を調べる
英小文字からなる非空文字列を作り、指定された語の出現回数に得点を掛けて足す。語は連続部分文字列として数え、出現が重なってもよい。例えば aaa に aa は二回現れる。得点には負数もあるので、単に長くするほど有利とは限らない。
入力にない語の得点を0とし、語 の一出現に対する得点を と書く。次の独自例で、一文字追加する前後を比べよう。
| 審査語 | a | b | ab | ba | aba | bab |
|---|---|---|---|---|---|---|
| 得点 | −2 | −1 | 4 | 3 | −2 | 1 |
ba に b を追加すると、既存の b、a、ba の出現はそのままである。増えるのは、新しい右端で終わる b、ab、bab の三つだけだ。従って増分は 。ba の得点0にこれを足して、bab の得点4になる。
一般に、末尾が の列へ を追加する増分は、
である。ここで は文字をつないだ語を表す。どの出現にも右端が一つあり、その右端を追加した瞬間だけ数えれば、重なる出現も漏れずに扱える。
末尾が同じなら、長い過去を忘れられる
末尾二文字が同じ二つの列に、同じ文字を付けてみる。増分は上の式で一致し、追加後の末尾も一致する。これを繰り返せば、どんな続きに対しても追加得点は等しい。従って、その二つの列は、今までの得点が高い方だけ残せばよい。
末尾一文字では足りない。例の aa と ba はどちらも a で終わるが、b を付けた増分はそれぞれ3と4である。違いは三文字語 bab が完成するかどうかにある。「審査語の最大長が3」という制約から、残すべき長さは2だと分かる。
状態を二文字の組 とすると、一文字追加は次の辺になる。
辺に、追加した文字と得点増分を持たせる。グラフ上の歩行、すなわち頂点の再訪を許す辺列が、そのまま文字列の生成手順である。
開始直後には二文字が存在しないので、入力に現れない記号 # で左側を埋め、始点を ## とする。# を含む語の得点は0とし、追加するのは英小文字だけにする。すると、最初の二文字でも同じ式が使える。
| 追加後の列 | 状態 | 今回の増分 | 累計 |
|---|---|---|---|
| 空列 | ## | — | 0 |
a | #a | −2 | −2 |
ab | ab | −1+4=3 | 1 |
aba | ba | −2+3−2=−1 | 0 |
abab | ab | −1+4+1=4 | 4 |
27種類の記号の二文字組をすべて用意すれば、頂点数は 。各頂点から26本の辺を張るので、辺数は である。例えば a# のような到達不能状態も含むが、始点から到達した状態だけを使えば問題ない。
「長くすれば儲かる」を閉路で捉える
表では、ab から a,b を追加すると再び ab へ戻り、得点は1から4へ増える。同じ二文字を何回でも追加でき、1周ごとに3点増えるので、この例の答えは Infinity だ。
一つの語に正の点が付いているだけでは、無限大とは限らない。例えば全単文字に−1、ab だけに+1なら、ab の得点は−1、繰り返すほど減点される。調べるべきなのは、ある状態へ戻るまでの増分の合計である。
始点から到達できる正の重みの閉路があれば、そこまで進んだ後、同じ閉路を繰り返せばよい。逆に正閉路がなければ、頂点を再訪する部分を取り除いても得点は下がらない。残るのは高々 辺の単純な道であり、長さ無制限でも有限の探索で最大値が求まる。
辺数を一つずつ増やし、改善が止まるかを見る
を「始点から高々 辺で頂点 に着く最大得点」とする。到達不能は と表す。初期値は始点だけ0、他は到達不能である。
一段の処理では、まず現在の配列を次の配列へコピーする。その後、各辺 の重みを として、現在の が有限なら、次を更新する。
読む配列と書く配列を分けると、一段が「辺を高々一本追加する」に一致する。これを 段行い、最後の段で一つでも値が増えたら Infinity。増えなければ、 の始点以外の有限値の最大を返す。途中の一段で更新がなくなった場合も、それ以降は同じなので終了できる。これはBellman–Ford法の緩和を最大化として行う方法である。
非空条件のため、始点の0を答えに混ぜない。# は追加できず、一度始点を離れたら戻れないので、始点以外の到達状態はちょうど非空文字列に対応する。
典型の発動条件
全体の評価を、最後の一操作の増分へ分ける
文字列を作る問題では、完成形を毎回評価する代わりに、「今回初めて数える対象は何か」を探す。出現を右端で分類すれば、同じ出現を二度数えず、過去の得点を確定できる。本問では長さ3以下という局所性によって、まだ未来に関与するのは末尾二文字だけになる。
最大語長が 、文字種数が なら、短い末尾をそのまま保存する状態数はおよそ である。 が小さい場合の有力な方法だが、長い語には指数的に増える。語が長くても本数が限られるなら、語の接頭辞と一致する末尾だけを残すAho–Corasickなどが候補になる。残す情報は、文字列の長さそのものではなく、未来の得点や判定へ影響する未完了部分で決める。
有限状態を作った後で、長さの条件に合う解法を選ぶ
同じ状態グラフでも、長さを固定するなら位置ごとのDP、長さが巨大で遷移が一定なら行列累乗、長さ無制限の最大化なら正閉路の判定を考える。状態が有限になっただけでは、歩行の長さまで有限になったとは言えない。
正閉路が答えへ影響するには、始点からそこへ到達できることが必要である。本問はどこで終了してもよいので、それだけで十分だ。終点指定の問題なら、閉路から終点へも到達できる必要がある。零閉路は何周しても同じ得点なので、最適な列を無限に多数作れても、最大得点は無限大にならない。
問題固有の要素
核心となる制約は、生成する列が長さ無制限なのに対し、審査語の長さは3以下という非対称性である。前者は反復の可否を、後者は一回の反復を記述する状態数を決める。両方を別々に読むことで、「無限個の候補を有限グラフへ移し、その閉路を調べる」という方針へ到達できる。
また、入力にない文字も生成できる。審査語に現れない文字を勝手に除くと、負の語の出現を避ける区切り文字を失う可能性があるため、全26文字の遷移を作る。
正当性
各審査語の出現を右端の位置へ割り当てると、各出現は一つの遷移の増分にだけ含まれる。開始時の # は得点に寄与せず追加もできないため、始点からの一辺以上の歩行と非空文字列は対応し、辺重みの総和は美しさに等しい。
高々 辺の歩行は、高々 辺の歩行、または高々 辺の歩行に最後の一辺を付けたものに分けられる。コピーと全辺の緩和はこの二つをすべて扱うので、二層更新は定義どおりの を計算する。
到達可能な正閉路がなければ、到達可能な閉じた歩行の重みは0以下である。歩行中の頂点の重複部分を除去しても得点は下がらず、同じ終点へ高々 辺で到達できる。始点には戻れないので、非空の歩行をこのように縮めても空にはならない。従って各状態の最大値は で得られ、 段目に改善はない。ゆえに最後の段に改善があれば正閉路が存在する。
逆向きも確認する。到達可能な正閉路があるのに 段目で改善しないと仮定する。閉路上の各頂点は単純な道でも到達できるため、 はすべて有限である。改善がないなら閉路の各辺について、
が成り立つ。閉路に沿って足すと左右の距離が相殺され、閉路重みが0以下になって矛盾する。従って正閉路は必ず検出され、その反復で得点を無限に増やせる。改善がない場合に始点以外の最大値を返す処理も、非空文字列の有限最大値を正しく求める。
実装上の注意
- 二文字組を整数へ符号化し、各辺の重みを先に計算する。緩和の内側で文字列の生成や辞書探索を繰り返す必要はない。
- 到達不能からは緩和しない。 の代用値に重みを足す処理も避ける。
- 各段は旧配列だけを読む。配列内でそのまま更新する実装もBellman–Ford法として可能だが、ここで説明した「高々 辺」という意味とは区別する。
- 一辺の絶対重みは最大 。 段までの値は絶対値 以下なので、重みもDPも符号付き64 bit整数にする。
- 全26単文字が−1なら答えは−1である。初期値0や、空文字列を最終候補へ混ぜないことをこの境界で確認できる。
復習の核
- 局所的な出現の総和は、追加した一文字を右端に持つ出現へ分ける。
- 残す末尾の長さは、次の増分を決めるために何文字必要かから導く。
- 長さ無制限の最適化では、到達可能な改善閉路と、零閉路を区別する。
- 状態グラフと開始・終了条件をセットで作る。非空条件を後から忘れない。
計算量と制約
時間
文字種数を とし、、 とする。得点表の初期化・入力は 、全辺の構成は 。二層Bellman–Ford法は、配列コピーも含め 時間なので、全体は 。本問のグラフでは最後の項は約1382万辺の緩和に相当する。
空間
長さ1〜3の語の得点表に 、辺一覧に 、二つのDP配列に を使い、全体で 。入力を得点表へ直接格納すれば審査項目の別保存は不要である。
制約との対応
、、。語の短さが729頂点・18954辺への圧縮を可能にする。得点が負にもなるため、正の辺の存在だけで無限大と判定せず、到達可能な正閉路を調べる。
出典
- 公式問題(2026-07-24T23:59:30+09:00確認) — source-abc264-g-problem-09dddce54ca2e241785fe37fb400d3c7bc821302dc9139e62bd5831725eae29f
- 個別公式解説(2026-07-24T23:59:30+09:00確認) — source-abc264-editorial-4580-9a15438df46f1a33d6d81400041f5950bad8c5ea8f0953e5f683c001e42709d2
分類・前提・執筆情報
掲載状態: 収録済み
最終確認:
学習上の位置付け
主題の単元: 有限状態automatonの構成
- 主題
- 有限状態automatonの構成: 未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。
- 追加で学ぶ技能
- 最短路モデル: 辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。
- 既習技能
主タグ: 有限状態automatonの構成 最短路モデル
執筆: abc-explanation-author1.1.1 / revision 5
学習の位置
体系上の位置: 有限状態automatonの構成
- 未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。
- 辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る