ABC 232 F — Simple Operations on Sequence

考察

ある要素を増減してから隣と交換する操作は、先に交換して移動先で同じ増減を行う操作へ入れ替えられる。したがって全交換を先、全増減を後に行ってよく、最終的に A のどの元要素を B の各位置へ対応させるかという順列を選ぶ問題になる。x を次に置くと、まだ未使用で x より小さい元添字は全て後ろへ来るので、その個数が x を左端とする転倒数としてこの時点で確定する。

棄却する候補: A の全順列を列挙し、転倒数による交換費用と B への増減費用を計算する。

N=18 でも N の階乗個の順列は列挙できない。

採用する候補: B の左から対応元を決め、既に使用した A の添字集合だけを状態とする subset DP を行う。

次に元添字 x を置く増減費用と、新たに確定する転倒数が使用済み集合と x だけから決まる。

操作の交換可能性で解を「順列+位置別補正」へ正規化し、順列の prefix で確定する転倒寄与を使用済みビット集合の遷移コストとして最短 DP を行う。

0-based で dp[0]=0、他を∞とする。maskで使用した元添字数 k=popcount(mask) が次の B の位置。未使用 x に対し

t = popcount((~mask) & ((1<<x)−1))
dp[mask|(1<<x)] = min(dp[mask|(1<<x)],
                     dp[mask]+X·abs(A_x−B_k)+Y·t)

とする。t は未使用で x より小さい元添字の数で、将来 x の後ろへ置く要素との転倒を一度だけ数える。答えは dp[(1<<N)−1]。費用は64bit整数で保持する。

典型の発動条件

操作順の正規化

発動条件: 二種類の操作が交換可能で、片方を全て先に寄せると最終構造を離散的に表せるとき。

交換を全て先にして A の順列を確定し、その後の増減費用を位置ごとの絶対差に分離する。

順列最適化の subset DP

発動条件: 順列を左から構成する追加費用が、使用済み要素集合と次要素だけに依存するとき。

mask の popcount を次の B 添字とし、未使用 x の対応費用と確定転倒数を加える。

問題固有の要素

増減費用は要素がどこへ移動したかだけ、交換費用は元添字順列の転倒数だけに依存し、操作列の細部を捨てられる。

別の問題へ持ち帰る視点: 値変更と位置変更が混在する最適化では、両操作を可換にして「対応」と「移動距離」の独立な費用へ分けられないか調べる。

正当性

操作をswapによる順序決定と値補正に正規化できる。使用maskの次に元index xを置くと補正費用と残った前方indexを追い越す転倒費用が確定する。全順列はこの選択列に一意対応し、最小隣接swap数は転倒数なのでsubset DP最小が全操作最小。

実装上の注意

  • mask の要素数を k とすると次の対応先は B_k であり、未使用かつ x より小さい添字数を Y 倍する。
  • Y と転倒数の積を含む費用は非常に大きいため 64 bit 整数と十分な INF を使う。

復習の核

  • 操作が任意順なら、隣接する異種操作を交換して一方を前へ寄せても結果と費用が保たれるかを確認する。
  • 順列の転倒数は完成後に数えるのでなく、次要素を置いた瞬間に確定する未使用要素との対として分配する。

計算量と制約

時間

列長N。maskN2^N遷移 O(N2^N)、各転倒増分を直接走査する実装は O(N²2^N)、popcountなら前者。

空間

maskDP O(2^N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 18; 1 \leq X \leq 10^8; 1 \leq Y \leq 10^{16}; 1 \leq A_i, B_i \leq 10^8; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Simple Operations on Sequence の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 部分集合・bitmask状態DP

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

      主タグ: 部分集合・bitmask状態DP

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

      学習の位置

      体系上の位置: 部分集合・bitmask状態DP

      • bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題