ABC 328 G — Cut and Reorder

考察

元の列をいくつかの連続区間に切り、その区間を出力の先頭から一つずつ置くと考える。次に置ける区間と置き先は、元のどの位置を使い終えたかだけで決まる。そこで使用済み位置の集合を状態にする。区間を探すときも、使用済み位置に当たった時点で右への延長を止めれば、無効な候補をすべて調べずに済む。

使用済み集合から次の出力位置を決める

複数回の分割・並べ替えも、途中で切った元の境界をまとめて一度だけ切り、最後と同じ順に並べれば再現できる。値の調整も最後にまとめてよい。この理由は「正当性」で確認する。

以下、配列の添字は 00 始まりとし、切り出した連続区間をブロックと呼ぶ。ブロックが qq 個なら、分割費用は (q−1)C(q-1)C である。並べ替えた後の各位置では、そこに置いた値と BB の値の絶対差だけ調整費用がかかる。

全順列を試すと最大 22!22! 通りあり、多すぎる。一方、出力を先頭から作る途中では、過去の具体的な順序を残す必要はない。使用済みの位置が同じなら、残っている位置も、次に埋める出力位置も同じだからである。

mask の第 ii ビットを、元の位置 ii を使い終えたときに 11 とする。dp[mask] を、その集合を使って出力の先頭部分を作る最小費用と定める。費用には、置いた要素の調整費用と、最初を除く各ブロックについての CC を含める。

popcount(mask) は立っているビットの数、すなわち使用済み要素数である。これを pp とすると、次のブロックの出力先は BpB_p から始まる。未使用の元の区間 [l,r][l,r] を追加する費用のうち、値の調整分は

∑t=0r−l∣Al+t−Bp+t∣\sum_{t=0}^{r-l}|A_{l+t}-B_{p+t}|

となる。最初のブロックには分割費用を加えず、mask が空でない場合だけ CC を加える。

右端を伸ばし、使用済み位置で打ち切る

各 mask で元の全区間を列挙してから重なりを判定すると、それだけで O(N22N)O(N^2 2^N) 時間になる。合法な区間だけを効率よく生成するには、左端 ll を固定し、右端 rr を ll から一つずつ右へ伸ばす。

位置 rr が使用済みなら、その場で break する。それより右へ伸ばした区間も同じ使用済み位置を含むため、調べる必要がない。未使用なら、新たに追加する ArA_r の対応先は Bp+(r−l)B_{p+(r-l)} である。この絶対差を足し、区間のビットを一つ立てれば、区間の調整費用と集合をそれぞれ O(1)O(1) で更新できる。本解説ではこの累積方式を採用し、区間と出力開始位置ごとの費用表は前計算しない。

次は実行用コードではなく、処理順を示す擬似コードである。I は追加する区間のビット集合、add はその調整費用を表す。

dp[0] ← 0; 他の状態は INF
for mask = 0, 1, ..., (1 << N) - 1:
    p ← popcount(mask)
    fee ← (mask = 0 なら 0、そうでなければ C)
    for l = 0, 1, ..., N - 1:
        I ← 0
        add ← 0
        for r = l, l + 1, ..., N - 1:
            if mask の第 r ビットが 1:
                break
            I ← I | (1 << r)
            add ← add + |A[r] - B[p + (r - l)]|
            next ← mask | I
            dp[next] ← min(dp[next], dp[mask] + add + fee)
答えは dp[(1 << N) - 1]

遷移では必ず未使用ビットが立つため、遷移先の整数値は mask より大きい。従って整数の昇順に処理すれば、更新元の最小値は確定している。

二つのブロックで回転させる小例

独自の小例として A=(1,2,3), B=(3,1,2), C=1A=(1,2,3),\ B=(3,1,2),\ C=1 を考える。ビットは右から元の位置 0,1,20,1,2 に対応させ、まず値 33 のブロック、次に値 1,21,2 のブロックを置く。

  • 最初は mask = 000、p=0p=0。区間 [2,2][2,2] を選ぶと、A2=3A_2=3 を B0=3B_0=3 に合わせる。調整費用も最初のブロックの費用も 00 なので、dp[100] = 0 となる。
  • 次は mask = 100、p=1p=1。l=0l=0 から伸ばすと、r=0r=0 では A0A_0 と B1B_1、r=1r=1 では A1A_1 と B2B_2 の差を累積する。どちらも 00 で、区間 [0,1][0,1] を追加すると dp[111] の候補は 0+0+C=10+0+C=1 になる。さらに r=2r=2 へ伸ばすと使用済みビットに当たるので打ち切る。

値としては [3],[1,2][3],[1,2] の順に置き、元の列を一か所切る費用 11 だけで一致する。分割しないと調整費用は 2+1+1=42+1+1=4 であり、少なくとも一度切る場合の費用は C=1C=1 以上なので、この例の最小値は 11 である。

典型の発動条件

subset DPへのblock append

出力を先頭から連続したブロック単位で作り、次の合法なブロックと追加費用が使用済み集合だけで決まるときに使う。本問では集合の大きさから出力開始位置も決まるので、最後に置いた位置を状態へ足さずに済む。

操作合成による一回化

複数回の分割・並べ替えを、途中で切った境界を集めた一度の分割で再現できるなら、操作列全体を探索せず、最終的な分割とブロック順を最適化する。再現する操作の費用が元の操作列以下になることまで確認する。

interval長別の遷移総数評価

未使用の連続区間を追加するときは、区間の長さを固定して、それを使える集合の数を数える。ただし、有効な遷移が少ないことだけでは実行時間は決まらない。使用済み位置で列挙を打ち切るなど、不採用候補を調べる費用も同じ上界に収まる手順が必要である。

問題固有の要素

要素を一つずつ追加して正確な分割費用を求めるなら、直前の元の位置とのつながりを知りたくなる。本問ではブロックを丸ごと追加し、その都度一定の費用を払うことで、直前の位置を保持せずに済む。元の順でつながる二つのブロックを余分に分ける表現も含むが、まとめて追加する安い遷移を残せば、最適値は保たれる。

他の問題でも、状態を増やす前に、何を一回の遷移としてまとめれば将来の費用を決められるかを考える。

正当性

元の列の各位置を区別して考える。複数回の並べ替えで切られた元の隣接位置の境界をすべて集めれば、その境界で一度だけ分割し、最後と同じ順にブロックを並べられる。集めた境界の数は実際に切った回数以下なので、費用は増えない。また、同じ要素への値の調整は最後にまとめても、絶対値の三角不等式により費用は増えない。従って、一度の分割・並べ替えと、その後の値の調整だけを最適化すればよい。

dp[mask] は、使用済み位置の集合が mask となるブロック列のうち、既に置いた要素の絶対差と、最初を除く各ブロックの費用を足した最小値である。同じ集合に至った過去の順序が違っても、次に使える区間とその出力先は等しいため、最小値だけを残せる。

左端を固定して右端を伸ばす列挙は、使用済み位置に当たるまでの未使用区間をすべて生成する。その位置を含む、さらに長い区間も使用済み集合と重なるため、そこで打ち切っても合法な遷移は失わない。遷移で加える絶対差は次の出力位置に対応し、ブロックが合計 qq 個なら追加費用はちょうど (q−1)C(q-1)C になる。

任意の分割とブロック順は、この遷移を順に選ぶことで再現できる。逆に、全位置を使うまで互いに重ならない元の区間を追加した遷移列は、実際の分割と並べ替えを表す。元の順で隣接する二つのブロックを別々に追加すると余分な費用がかかるが、それらを一つにまとめる遷移も存在する。従って最小化では最適解を失わず、全位置を使用した状態の値が求める最小費用である。

実装上の注意

  • 使用済みビットの検査は、Bp+(r−l)B_{p+(r-l)} を読む前に行う。有効な区間の長さは残りの要素数以下なので添字は範囲内に収まるが、使用済み位置で打ち切る際には、その対応先が存在するとは限らない。
  • add と I は左端を変えるたびに初期化する。右端を一つ伸ばすごとに絶対差を一つだけ足し、区間全体を走査し直さない。
  • 最初のブロックは無料とし、dp[0] = 0 と組み合わせる。全遷移で CC を足す方式と混ぜない。
  • 費用には符号付き64ビット整数を使う。調整費用と分割費用の合計は N(1015−1)+(N−1)C<4.3×1016N(10^{15}-1)+(N-1)C<4.3\times10^{16} なので、例えば INF = 1 << 60 なら上限に余裕がある。ビット演算に使う整数型も明示する。
  • N=1N=1 では一要素のブロックを無料で追加し、答えは ∣A0−B0∣|A_0-B_0| となる。元の順を保つ一ブロックも、mask = 0 から全区間を追加する遷移として必ず含まれる。

復習の核

  • 出力位置が使用済み要素数だけで決まるなら、過去の並び順を集合へ圧縮できないか考える。
  • 遷移の総数を数えたら、無効な候補の検査回数も数える。連続区間は最初の禁止位置で延長を止められる。
  • ブロックごとの課金では、最初を無料にする初期化と、ブロック数から一を引く費用式を対応させる。

計算量と制約

時間

時間計算量は O(N2N)O(N2^N) である。各有効区間の追加では、ビット集合・累積費用・DPの更新をそれぞれ O(1)O(1) で行う。

長さ kk の区間は N−k+1N-k+1 個ある。その区間の全ビットが未使用である mask は、外側の N−kN-k ビットを自由に選べるため 2N−k2^{N-k} 個ある。従って全 mask にわたる有効な区間追加の総数は

∑k=1N(N−k+1)2N−k=2N(N−1)+1\sum_{k=1}^{N}(N-k+1)2^{N-k}=2^N(N-1)+1

となる。一方、使用済み位置に当たって打ち切る検査は、各 (mask, l) につき高々一回であり、合計 N2NN2^N 回以下である。左端ごとの初期化も N2NN2^N 回で済む。これらを合わせて初めて、列挙全体が O(N2N)O(N2^N) 時間と評価できる。

popcount は一ワードの命令を使えば O(1)O(1) である。使わずに各 mask のビットを O(N)O(N) で数えても、全体の時間計算量は変わらない。

空間

空間計算量は O(2N)O(2^N) である。DP表が 2N2^N 要素、入力配列が O(N)O(N) 要素で、区間の費用とビット集合は走査中の変数だけで保持する。区間費用の O(N3)O(N^3) の前計算表は不要である。

制約との対応

公式制約は 1≤N≤221\leq N\leq22、1≤C,Ai,Bi≤10151\leq C,A_i,B_i\leq10^{15}、制限時間は2.8秒、メモリ制限は512 MiBである。集合は一ワードの整数に収まり、ビット演算は定数時間で行える。

N=22N=22 では有効な区間追加は 88,080,38588{,}080{,}385 回であり、DP表を64ビット整数で持つと32 MiBになる。全区間を毎回検査せず、早期打ち切りと定数時間の累積更新を行うことが、この上限で処理するための要点である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Cut and Reorder の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題