ABC 381 E — 11/22 Subsequence

考察

長さ2m+1の 11/22 部分列が区間に存在するなら、より小さい m でも存在するので m に単調性がある。中央の / を選び、その左に1がm個、右に2がm個あるかを位置列で判定できる。

採用する候補: 文字1,2,/の出現位置列を前計算し、各 query で m を二分探索して、必要な m 個目の1・次の/・m個目の2が区間内に収まるか判定する。

棄却する候補: 各 query の区間を走査し、全ての / を中央候補として左右の個数を調べる。

区間長の総和が O(NQ) になり、N,Q≤10^5 に間に合わない。

各文字の位置 vector を作る。query [L,R] の feasible(m) を三回の lower_bound/index 加算で実装し、最大 m を二分探索する。存在すれば2m+1、/すらなければ0を返す。

典型の発動条件

部分列長の二分探索

発動条件: 長さ parameter を小さくすると必ず成立し、固定長部分列を位置列で判定できるとき。

貪欲に最早位置を選ぶ判定で最大 m を探す。

問題固有の要素

部分列の中央記号が固定される形では、左右に必要な同文字数を parameter にすると単調判定になる。

別の問題へ持ち帰る視点: 存在判定では各段階を最も早く選ぶことが将来の余地を最大化する。

正当性

m を固定すれば、左端以降の m 個目の1を最も早く取り、その後の最初の/、さらに m 個目の2を最も早く取る貪欲判定が必要十分である。 空でない 11/22 は必ず / を一つ含み、m=0 の文字列 / も答え候補なので slash 不在時だけ0になる。 出現位置への lower_bound で一判定 O(log N)、外側の二分探索を含めても O(log^2 N) で10^5 queryを処理できる。

実装上の注意

  • m=0 と slash 不在を区別し、vector の添字超過を都度確認する。query の L,R は閉区間である。

復習の核

  • 固定 m の最早選択を実際の位置列で追い、遅い候補を選ぶ利点がないことを交換論法で確認する。

計算量と制約

時間

O(N+Q log N log N)、m二分探索ごとに三回の位置lower_bound。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^5; 1 \leq Q \leq 10^5; S is a string of length N consisting of 1, 2, and /.; 1 \leq L \leq R \leq N; N, Q, L, and R are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

11/22 Subsequence の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 単調境界を証明して探索する

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

      主タグ: 単調境界探索

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

      学習の位置

      体系上の位置: 単調境界を証明して探索する

      • 判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。

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

      • 連続窓の両端を一方向に進める尺取り法、および真偽判定の単調境界を持たない三分探索・局所探索。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題