ABC 268 F — Best Concatenation

考察

string iの内部scoreは連結順に依存せず、順序で変わるのは前stringのXと後stringのdigitのcross寄与だけである。

string iのX個数をX_i、digit和をY_iとすると、iをjより前へ置くcross寄与はX_iY_jになる。

棄却する候補: N!通りの連結順を試し、各完成stringのscoreを走査する。

permutation数が階乗的で、各pairの局所順序比較だけで決まる構造を使っていない。

採用する候補: 隣接交換比較により iをjより前に置く条件 X_iY_j≥X_jY_i を導き、このcross-product comparatorで全stringをsortする。

pairwise separable concatenation objectiveにexchange argumentを適用し、Smith-rule型のratio orderingへ変換する。

典型の発動条件

隣接交換による最適sort順

発動条件: 連結順の目的値がstring内部定数と順序付きpair寄与の和に分解できるとき。

二要素ijとjiの差を計算し、改善交換がなくなる比較規則でsortする。

比率比較のcross multiplication

発動条件: 非負整数pairの比a/bでsortしたいが、0除算や浮動誤差を避けたいとき。

a_i b_jとa_j b_iの整数積を比較する。

問題固有の要素

X_i=0の数字だけのstringはratio Y_i/X_i=∞として後ろに置かれ、cross-product comparatorなら例外分岐なしで同じ結果になる。

別の問題へ持ち帰る視点: ratio順の境界値は数学的に解釈しつつ、実装はcross productで統一する。

正当性

順序ijとjiのscore差はX_iY_j−X_jY_iで、比Y_i/X_iの昇順に相当するが除算せずcross productで比較できる。 条件に反する隣接pairは交換でscoreを改善できるため、全pairがcomparator順になった列がglobal optimumになる。

実装上の注意

  • sort後は左からX累積数を持ち、digit dごとにd×累積Xを加えれば内部・cross寄与を一走査で同時に数えられる。
  • cross productとscoreは32 bitを超えるため64 bit整数を使い、比較が等しいpairは任意順でよい。

復習の核

  • 連結順最適化は、二つのblockだけを入れ替えた目的値差から全体sort comparatorを導く。
  • block間寄与が「左の量×右の量」なら、内部寄与を切り離してexchange argumentを試す。

計算量と制約

時間

O(N log N+L)、Lは総文字数、cross-product sort。

空間

O(N+L)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; N is an integer.; S_i is a string of length at least 1 consisting of digits from 1 through 9 and the character X.; The sum of lengths of S_1, S_2, \ldots, S_N is at most 2 \times 10^5.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

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

      主タグ: 貪欲法と交換論

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

      学習の位置

      体系上の位置: 交換論から選択順を導く

      • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

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

      • 対称操作による状態の正規化。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題