ABC 300 F — More Holidays

考察

周期文字列T=S^Mの最適区間の始点は、全変更と区間をNだけ左へ平行移動できるため最初の一周期内に選べる。

採用する候補: N始点列挙と終点二分探索

棄却する候補: 長さNMのTを構築して尺取

Mは10^9で展開不能。

i=0..N-1ごとにendを[i,NM]で二分探索し、prefixX(end)-prefixX(i)≤Kとなる最大end-iを答えへ取る。

典型の発動条件

周期列のprefix集約

発動条件: 巨大な繰返し列の区間頻度が必要。

完全周期数と余りprefixへ分ける。

最遠到達二分探索

発動条件: 固定始点で区間costが終点に単調。

K以下となる最大終点を求める。

問題固有の要素

周期対称性でNM個の始点をN個へ落とし、終点だけ巨大座標で探せる。

別の問題へ持ち帰る視点: 周期列の部分区間最適化は始点を一周期に正規化する。

正当性

変更すべきx数だけが区間可否を決め、prefixX(pos)=floor(pos/N)·cntX+一周期prefixで巨大位置も計算できる。 周期prefixで任意長区間のx個数をO(1)計算でき、各始点からK個以下となる最遠端を単調判定で求められる。

実装上の注意

  • 終点は半開区間でNMまで、Kは全x数以下だが区間長を64ビットで持つ。

復習の核

  • 短い展開列の尺取と比較し、K=0、周期境界跨ぎ、全x・x一個周期、区間が全Tになる例を確認する。

計算量と制約

時間

O(N log(NM))、一周期N始点ごとの終端二分探索。

空間

O(N)、一周期のx-prefix。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: N, M, and K are integers.; 1 \le N \le 3 \times 10^5; 1 \le M \le 10^9; 1 \le K \le x, where x is the number of x's in the string T.; S is a string of length N consisting of o and x.; S has at least one x.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

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

    主タグ: 単調境界探索

    補助タグ: 累積和・差分配列

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題