ABC 329 E — Stamp

考察

forwardの上書き順を逆に見ると、現在文字列のwindowが各位置でTと一致するか既に消した#なら、そのwindowを全て#へ戻せる。

#化はwindowの一致条件を緩めるだけなので、現在使えるwindowを今消しても将来の可能性を損なわない。

1つのwindowを#化して新たにgoodになり得るのは、そのM文字と重なる開始位置だけである。

採用する候補: reverse操作でgood windowをqueue管理し、使えるwindowを単調に#化して全消去できるか判定する。

棄却する候補: forwardに#列からstamp位置をgreedyに選ぶ。

後のstampが前の文字を上書きするため、途中状態と最終Sの局所一致だけでは安全な選択を決めにくい。

棄却する候補: 現在Tと完全一致するsubstringだけをreverse消去する。

既に#になった位置は以前のstampで上書き済みとしてwildcardにでき、完全一致だけでは必要なoverlapを見落とす。

current=Sとし、全start 0..N-Mでgoodならqueueへ入れる。queueからiをpopし未使用ならusedにしてwindow内の文字を#へ変える。各変更位置pについてstart∈[p-M+1,p]を範囲clipしてgoodか再検査し、成立windowをenqueueする。終了後currentが全#ならYes、そうでなければNo。

典型の発動条件

操作の逆転

発動条件: forward操作が上書きで履歴依存だが、最終状態から戻すと削除になるとき。

stampを最後に押したwindowからwildcard #へ戻す。

monotone queue propagation

発動条件: 状態変更が条件を緩和し、新たに可能になった局所操作を処理するとき。

good windowをqueueへ追加して固定点まで回す。

局所影響範囲の再検査

発動条件: 長さM window操作で条件が変わる候補がoverlap範囲だけのとき。

変更文字を含むO(M)個のstartだけを見る。

問題固有の要素

reverse状態の#は文字が決まっていないのではなく、「より後のforward stampに上書きされたので何文字でもよい」というワイルドカードを表す。

別の問題へ持ち帰る視点: 上書き構成問題では、逆向きに消した位置をwildcard化すると操作可否が単調になることがある。

正当性

window iがgoodとは全jでcurrent[i+j]=='#'またはT[j]であることで、これはそのstampが最後に押されたとみなせる必要十分条件である。 各windowは一度処理すれば全#になり、再度処理しても変化しないのでused flagでqueue重複を無害化できる。 上書き履歴をmonotoneな削除過程へ変え、局所更新だけで全候補を伝播できる。

実装上の注意

  • window startを0..N-Mへclipし、M≤5を利用してgood判定を直接O(M)で行う。
  • 既に#の文字を再変更せず、used windowを二重処理しないことで無駄なqueue増殖を防ぐ。

復習の核

  • 完全一致windowを消した後、#とのoverlapによって別windowがgoodになる例を作り、再検査start範囲とwildcard条件を確認する。

計算量と制約

時間

O(NM²)、各文字は一回#へ変わり、影響する最大M windowをO(M)で再検査。

空間

O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2\times 10^5; 1 \leq M \leq \min(N, 5); S is a string consisting of uppercase English letters with length N.; T is a string consisting of uppercase English letters with length M.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 時間を逆向きにして未来依存を消す

主題
追加で学ぶ技能
    なし
    既習技能
    • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。

    主タグ: 逆向きのオフライン処理

    補助タグ: 単調進行による償却解析

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

    学習の位置

    体系上の位置: 時間を逆向きにして未来依存を消す

    • 時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。

    先に読む単元:

    • 単調進行による償却解析 — 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

    • 値順eventを前から処理するsweep、時刻を反転せずに行う通常のonline更新、および答えの局所寄与だけを集計する順序交換。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題