ABC 338 G — evall

考察

右端を一文字ずつ伸ばすと、それまでに選んだすべての左端に同じ文字が追加される。各式を「加算が確定した部分」と「まだ伸びる乗算項」に分ければ、この共通の変化を少数の合計値だけで追える。数字を読んだ時点で、その位置を右端とする式の値をまとめて答えへ加えよう。

文字列の長さを L=∣S∣L=|S| とする。数字だけの入力でも部分文字列は L(L+1)/2L(L+1)/2 個あり、L≤106L\leq 10^6 では個別に評価できない。一方、右端を固定すると、以前の数字位置から始めた式を延長する処理は共通である。まず一つの左端について更新を考え、それを全左端について足し合わせる方針を試す。

一つの式をどう延長するか

通常の演算優先順位では、+ で区切られた乗算項を足し合わせる。そこで、ある数字位置から現在位置までを読んだ状態を次の量で表す。

  • pre\mathrm{pre}: 最後に読んだ + までに確定した乗算項の和。+ がなければ0。
  • num\mathrm{num}: 今読んでいる数。数字を続けて読む間は十進数として連結する。
  • mul\mathrm{mul}: 現在の乗算項で、num\mathrm{num} より前にある因子の積。まだ因子がなければ1。
  • term=mul⋅num\mathrm{term}=\mathrm{mul}\cdot\mathrm{num}: 現在の乗算項。

数字を読んだ直後なら、式の値は pre+term\mathrm{pre}+\mathrm{term} である。例えば 1+2*3 では、pre=1, mul=2, num=3, term=6\mathrm{pre}=1,\ \mathrm{mul}=2,\ \mathrm{num}=3,\ \mathrm{term}=6。次に 4 を連結すると、現在の数が34になり、式の値は69になる。

数字 dd の連結は num′=10num+d\mathrm{num}'=10\mathrm{num}+d なので、

term′=10term+d⋅mul\mathrm{term}'=10\mathrm{term}+d\cdot\mathrm{mul}

となる。+ を読んだら現在項を確定して pre\mathrm{pre} に足し、次の乗算項の係数を1へ戻す。* を読んだら現在項を次の数に掛ける係数へ引き継ぐ。どちらの演算子でも、次の数を待つため num=0, term=0\mathrm{num}=0,\ \mathrm{term}=0 にする。この0は待機状態を表すもので、演算子で終わる式の評価値ではない。

1+2* の段階では pre=1, mul=2, term=0\mathrm{pre}=1,\ \mathrm{mul}=2,\ \mathrm{term}=0 として次を待つ。ここで2を加算済みにしてしまうと、続く 3 を掛けるべき相手を失う。確定するのは + を読んだときだけである。

全左端を四つの集計値へまとめる

処理済みの各数字位置を左端に選び、そこから現在位置まで延長している状態をすべて残す。状態数を cnt\mathrm{cnt} とし、各状態の pre,mul,term\mathrm{pre},\mathrm{mul},\mathrm{term} の総和をそれぞれ preSum,mulSum,termSum\mathrm{preSum},\mathrm{mulSum},\mathrm{termSum} と呼ぶ。左端ごとの値や num\mathrm{num} 自体を保存する必要はなく、この四つだけで次の更新が閉じる。

最初は状態が一つもないので、四つの集計値と答え answer\mathrm{answer} をすべて0にする。以下のプライム付きの値は更新後、右辺はすべて更新前の値を表す。実装では必要な旧値を保存して同時更新する。

数字 dd では、既存状態の連結に加えて、その位置を新しい左端とする一文字の式を追加する。新状態は (pre,mul,term)=(0,1,d)(\mathrm{pre},\mathrm{mul},\mathrm{term})=(0,1,d) なので、

cnt′=cnt+1,preSum′=preSum,mulSum′=mulSum+1,termSum′=10termSum+d⋅mulSum+d.\begin{aligned} \mathrm{cnt}'&=\mathrm{cnt}+1,\\ \mathrm{preSum}'&=\mathrm{preSum},\\ \mathrm{mulSum}'&=\mathrm{mulSum}+1,\\ \mathrm{termSum}'&=10\mathrm{termSum}+d\cdot\mathrm{mulSum}+d. \end{aligned}

最後の +d+d が新しい左端の寄与である。新状態を含めた更新後の値から、

answer′=answer+preSum′+termSum′\mathrm{answer}'=\mathrm{answer}+\mathrm{preSum}'+\mathrm{termSum}'

とする。先に mulSum\mathrm{mulSum} を増やしてから旧値用の式へ代入すると、新状態を二度足してしまう。

+ では各状態の現在項を加算済みにし、各状態の係数を1にする。係数の総和は状態数になるので、

cnt′=cnt,preSum′=preSum+termSum,mulSum′=cnt,termSum′=0.\begin{aligned} \mathrm{cnt}'&=\mathrm{cnt},\\ \mathrm{preSum}'&=\mathrm{preSum}+\mathrm{termSum},\\ \mathrm{mulSum}'&=\mathrm{cnt},\\ \mathrm{termSum}'&=0. \end{aligned}

* では加算済み部分に触れず、各状態の現在項を次の係数にするので、

cnt′=cnt,preSum′=preSum,mulSum′=termSum,termSum′=0.\begin{aligned} \mathrm{cnt}'&=\mathrm{cnt},\\ \mathrm{preSum}'&=\mathrm{preSum},\\ \mathrm{mulSum}'&=\mathrm{termSum},\\ \mathrm{termSum}'&=0. \end{aligned}

この代入には旧 termSum\mathrm{termSum} が必要である。0へ戻す前に読み取る。両方の演算子で現在項を0へ戻し、新しい左端は作らず、答えも増やさない。演算子を右端とする部分文字列の値は問題の定義で0だからである。最後の数字まで処理した answer\mathrm{answer} が答えとなる。加算・乗算だけの更新なので、途中からすべて法998244353で計算してよい。

1+2*34 の状態を追う

入力例1を一文字ずつ処理すると次のようになる。表は更新後の集計値で、演算子の行も次の数字へ引き継ぐ状態を示す。先頭行はまだ文字を読んでいない初期状態である。

文字cnt\mathrm{cnt}preSum\mathrm{preSum}mulSum\mathrm{mulSum}termSum\mathrm{termSum}寄与answer\mathrm{answer}
—0000—0
1101111
+1110—1
2212456
*2140—6
3315151622
4416174175197

2 を読んだ時点の式は 1+2 と 2 で、寄与は 3+2=53+2=5。* の後も加算済みの1はそのまま残り、次の係数はそれぞれ2となる。続く 3 では 1+2*3, 2*3, 3 の値を足して 7+6+3=167+6+3=16 になる。

さらに 4 を読むと、既存の三つは 1+2*34, 2*34, 34 へ延び、それぞれ69、68、34となる。加えて、4 の位置から始まる一文字の式も必要である。左端は数の先頭に限られず、二桁の34の途中からでも選べるため、寄与は 69+68+34+4=17569+68+34+4=175。右端ごとの寄与を合計した 1+5+16+175=1971+5+16+175=197 が入力例1の出力と一致する。

典型の発動条件

式評価stateの線形集約

発動条件: 多数の候補へ同じ文字・操作を適用し、個別状態の更新を足し合わせると少数の総和と個数だけで次の値を求められる。

まず一候補の遷移を導き、総和を取って必要な補助量を探す。本問では数字の連結に係数の総和、+ に候補数が必要になる。現在の答えを出せるだけでなく、次の更新にも十分かを確かめる。

乗算優先順位の遅延評価

発動条件: 括弧のない加算・乗算を、乗算を優先して左から評価したい。

加算済み部分と現在の乗算項を分離する。* では現在項を次の因子に掛ける係数へ引き継ぎ、+ で初めて加算済みにする。減算・除算・括弧などを許す別問題では、その演算でも同じ状態が十分かを考え直す。

問題固有の要素

有効な左端と右端がどちらも数字位置なので、数字を読むたびに「新しい左端を一つ追加する」「そこを右端とする全候補を数える」を行える。演算子の直後は候補の延長に必要な待機状態だけを保つ。この開始・終了の条件と、通常の演算優先順位の両方を状態設計へ反映する点が本問の要所である。

正当性

本稿の四集計値による方法は、公式解説の数字ごとの左右の寄与を分解する方法とは異なる。ここでは公式問題文の評価規則から、次の不変条件を示す。

各文字の処理後、処理済みのすべての数字左端について、一つずつ延長状態が存在すると考える。各状態の加算済み部分が pre\mathrm{pre}、最後の乗算項の既読因子の積が mul\mathrm{mul}、現在数が num\mathrm{num} で、term=mul⋅num\mathrm{term}=\mathrm{mul}\cdot\mathrm{num} を満たす。演算子直後は次の数を待つ num=term=0\mathrm{num}=\mathrm{term}=0 の状態とする。四集計値は、この状態集合の個数と各成分の総和に等しいものとする。

初期状態は空集合なので、四つとも0で条件を満たす。数字を読む場合、各既存状態では十進連結の式に従って現在項が更新され、新しい左端の状態 (0,1,d)(0,1,d) がちょうど一つ加わる。+ では現在項を加算済みにして係数を1へ戻し、* では現在項を次の係数へ引き継ぐ。いずれも通常の演算優先順位に従う一候補の更新であり、これらを全候補について足したものが本文の集約式である。従って不変条件は次の文字の処理後も保たれる。

数字を右端とするとき、すべての状態は有効な式で、その値の総和は更新後の preSum+termSum\mathrm{preSum}+\mathrm{termSum} に等しい。任意の両端が数字の部分文字列は、左端を読んだときに生成され、右端を読んだときに一度だけ答えへ加わる。演算子を端点とする部分文字列は定義上0であり、加算の対象にしない。よって最後の answer\mathrm{answer} は求める総和である。更新は加算・乗算のみなので、各段階で法998244353の剰余に置き換えても答えの剰余を保つ。

実装上の注意

  • 数字の式の右辺には更新前の mulSum\mathrm{mulSum} を使い、答えには更新後の termSum\mathrm{termSum} を使う。* では旧 termSum\mathrm{termSum} を係数へ移してから0にする。
  • + と * では候補数と答えを変えない。演算子直後の待機状態を式の値として足さない。
  • 入力が一桁 dd なら最初の数字更新だけで答えは dd になる。演算子がなくても各数字で新しい左端を追加し、数字列の全部分文字列を数えられる。
  • 積を取る前に剰余を保ち、積や和を計算する整数幅に注意する。64 bit整数なら、本稿の 10termSum+d⋅mulSum+d10\mathrm{termSum}+d\cdot\mathrm{mulSum}+d を安全に計算できる。

復習の核

  • 全部分文字列の和では、右端を固定したときの共通更新を探す。一候補の式から始め、総和の更新に必要な補助量を追加する。
  • 現在の評価値だけでは桁連結や乗算を続けられない。加算済み部分・乗算係数・現在項に分け、次の文字でも更新が閉じることを確かめる。
  • 新しい左端は数字ごとに追加する。1+2*34 の最後では、34 だけでなく 4 も数える。演算子直後の待機状態は答えへ足さない。

計算量と制約

時間

入力の読込みを含めて O(L)O(L)。各文字で四つの集計値と答えを定数回の演算で更新し、前処理や左端ごとの走査は行わない。

空間

入力文字列を保持する場合、入力込みで O(L)O(L)、集計値と一時変数だけの補助領域は O(1)O(1)。候補の状態や桁の累乗表は保存しない。

制約との対応

1≤L≤1061\leq L\leq 10^6 に対して一走査で済む。文字は1〜9の数字と +, * のいずれかで、先頭・末尾は数字、演算子どうしは隣接しない。このため数字の左端から数字の右端まで切り出せば常に通常の式になり、演算子直後の待機状態には必ず次の数字が続く。答えは998244353で割った余りを求める。制限時間は2秒、メモリ制限は1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: DP遷移を因数分解・集約して加速する

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

      主タグ: DP遷移の集約・高速化

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

      学習の位置

      体系上の位置: DP遷移を因数分解・集約して加速する

      • 遷移式を属性別極値・少数の重み付き和へ分解し、その集計値が更新について閉じることを示せる。

      先に読む単元:

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

      • 固定線形遷移の巨大回累乗。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題