ABC 229 G — Longest Y

考察

Y の位置を昇順に A_i とすると、連続した Y を作る際にも Y 同士の順序は交換せず、採用する Y は A 上の連続区間としてよい。

B_i=A_i−i とずらすと、隣接する目標位置の一マス差が消え、選んだ B_i を同じ整数へ動かす総距離が交換回数になる。

棄却する候補: 各交換をシミュレーションし、現在最も長くなりそうな Y の塊へ近い Y を一つずつ寄せる。

K が 10 の 12 乗まであり、局所的な交換選択だけでは最適な採用区間も保証できない。

採用する候補: 長さ m を二分探索し、B の各長さ m 区間を中央値へ揃える費用を累積和で計算して K 以下か判定する。

m 個を連続化できればそれ未満もでき、絶対値和は中央値で最小になるため各窓を定数個の区間和で評価できる。

目標の連続座標を直接最適化せず、Y の順位 i を位置から引くことで「全要素を一値へ揃える」中央値問題に正規化する。

Y の位置列を順位補正して単調列 B を作り、長さ m の各窓について中央値までの L1 距離を prefix sum で求める可否判定を答えの二分探索に使う。

典型の発動条件

連続配置の順位補正

発動条件: 順序を保った点を間隔 1 の連続位置へ移す最小総移動量を求めるとき。

i 番目の位置 A_i から i を引き、連続配置を同一点への移動へ変換する。

中央値による絶対値和最小化

発動条件: 複数の値を一つの共通値へ動かすコストが絶対差の総和であるとき。

各窓の中央要素を目標にし、左右の費用を累積和から求める。

長さの単調可否に対する答え二分探索

発動条件: 長さ m の対象を予算内で構成できれば、それより短い対象も構成できるとき。

各長さ m の窓を中央値へ揃える最小費用が K 以下か判定し、可能な最大 m を二分探索する。

問題固有の要素

Y の相対順序は隣接交換で入れ替える必要がなく、離れた Y を飛ばして採用するより間の Y を採用する方が移動費用を悪化させない。

別の問題へ持ち帰る視点: 一次元の順序保存移動では、最適な採用集合が元の順序上の連続区間になる交換論法を検討する。

正当性

Yの順序を保って連続位置へ移すと、必要な隣接交換数は各Yの移動量の総和になる。順位補正後はその最小値を中央値が達成する。全窓を調べれば最安の連続化を拾え、可能な長さの部分区間も可能なので二分探索が正しい。

実装上の注意

  • A_i と i の添字基準を統一すれば定数ずれは全 B に共通なので費用へ影響しないが、窓の中央添字は一貫させる。
  • 位置差の総和と K は大きくなるため 64 bit 整数を使い、Y が一個もない場合も答え 0 を返す。

復習の核

  • 点を間隔 1 で並べたいときは、目標位置列の傾き 1 を順位分だけ引いて水平化する。
  • 最大個数を求める前に、固定個数の最小費用が連続窓と中央値で求まるかを切り分ける。

計算量と制約

時間

O(N+Y log Y)、N文字列長YはY文字数。各長さ判定はprefix中央値距離O(Y)。

空間

O(Y)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq |S| \leq 2 \times 10^5; Each character of S is Y or ..; 0 \leq K \leq 10^{12}; K is an integer.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

主題
追加で学ぶ技能
    なし
    既習技能
    • 一次元凸・単峰最適化: 差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 単調境界探索

    補助タグ: 一次元凸・単峰最適化

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

    学習の位置

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

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

    先に読む単元:

    • 一次元凸・単峰最適化 — 差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題