ABC 302 G — Sort from 1 to 4

考察

任意の二位置を交換できるので、隣接交換に対する転倒数は今回の費用を表さない。完成列Bは昇順列として一意に決まる。各値の頻度からBの四つの区間をO(N)で作り、C[i][j]を「現在値i、目標値jの位置数」とする。同じ型の位置は交換の効果が同じだから4×4へ集約できる。

正しい位置C[i][i]を除き、誤配置i→jを重みC[i][j]の辺と見る。現在列と目標列では各値の個数が同じなので、各頂点の入る重み和と出る重み和は等しい。この均衡は閉路分解の手掛かりになる。逆向きのpair i→j,j→iは一交換で直せるが、これだけでは3-cycleや4-cycleが残る。

最適回数の下界を先に探す。値の順序p=(p_1,…,p_4)を一つ固定し、その順序で前から後へ向かう誤配置の総量をF(p)=Σ_{a<b}C[p_a][p_b]とする。一交換でこの量は高々1しか減らないからF(p)回以上必要である。4種類なら24順列を全て調べ、最も強い下界max_p F(p)を取れる。

ただし下界を計算しただけで最適とは言えない。正当性節では、逆向きpairを消す操作が全pのFを一律1ずつ減らすこと、残った4頂点の均衡graphが二種類の3-cycleと一種類の4-cycleへ分かれることを示す。その具体的な交換列が、あるpのFと同じ回数で全誤配置を直す。これで初めて下界を回答として使える。

実装は位置ごとのCを作り、24順列それぞれの6個の前向き成分を足して最大値を出すだけでよい。閉路分解はこの式の達成可能性を証明するための構成で、実装で交換列を出力する必要はない。

典型の発動条件

小さい値域への頻度圧縮

発動条件: 列長は大きいが、交換の振る舞いが現在値と目標値の組だけで決まる。

各位置を4×4の誤配置型へ集約し、位置列を定数サイズの状態へ落とす。

有限全探索によるpotential最大化

発動条件: 値種類数が4で、順序を固定した下界を全順序から選べる。

24通りの順列を列挙し、swap一回あたり変化量が1以下のpotentialの最大を取る。

問題固有の要素

二要素の直接相殺だけでなく、3-cycle・4-cycleとして残る誤配置も、値順序pに対する向き付き誤配置数で一括して数えられる。

別の問題へ持ち帰る視点: 任意交換による分類修正は、誤配置flowと、一操作で高々1変わる順序potentialから最適回数を証明できることがある。

正当性

まず下界を示す。p内の順位をw,x,y,zとして、現在値p_w・目標値p_xの位置と、現在値p_y・目標値p_zの位置を交換する。C[p_w][p_x],C[p_y][p_z]が1ずつ減り、C[p_y][p_x],C[p_w][p_z]が1ずつ増える。Fから二項とも減るのはw<x,y<zのときだけ。そのときw≤yならw<z、w>yならy<xなので、少なくとも一つの増加項もFへ入る。減少項が一つ以下なら減少量も一つ以下である。従って一交換でFは高々1しか減らず、完成列のF=0から全てのpについてF(p)が必要回数の下界になる。

次に達成する交換を構成する。逆向きpair i→j,j→iを一組交換すると両位置が正しくなり、全てのpでちょうど一方の辺がFに入るため、F(p)は一律1減る。この交換をd回行って相殺し切る。残るgraphは各無順序対に高々一方向だけがあり、各頂点の重みの入出が均衡する。

残辺は全て有向閉路へ属する。実際、強連結成分を縮約したDAGのsourceは外からの流入がなく、成分の均衡より外への流出も0なので、成分間の正辺は存在しない。逆向きpairがないので非自明な強連結成分には3頂点以上が要り、4頂点全体では高々一つである。残辺がなければ追加費用0。3頂点だけが活動していれば有向三角形となる。孤立した第四頂点へ三角形の一頂点から辺を入れ、第四頂点から別の頂点へ辺を出す向きを与え、欠けた辺の重みを0とすれば、4頂点の強連結tournamentへ補える。4頂点が活動している場合も、欠けた辺へ任意の向きと重み0を与えれば強連結性を保つ。これは証明用の補完で、誤配置や費用は増やさない。

4頂点の強連結tournamentでは各頂点の出次数は1か2、総辺数6より各二頂点ずつである。出次数2の二頂点をp_1→p_2、出次数1の二頂点をp_3→p_4となるように名付ける。p_2はp_1へ出られないのでp_3,p_4へ出る。p_3は既にp_4へ出るのでp_1へ出られず、残りもp_1→p_3,p_4→p_1と確定する。ここで値種類が4である条件を使っている。

p_1→p_3,p_2→p_3,p_2→p_4の重みをa,b,c≥0と置く。各頂点の均衡式から残りは

p_1→p_2: b+c
p_3→p_4: a+b
p_4→p_1: a+b+c

になる。従ってこの誤配置は次の閉路の和として全て使い切れる。

  • a組の(p_1→p_3→p_4→p_1):各2交換。
  • b組の(p_2→p_3→p_4→p_1→p_2):各3交換。
  • c組の(p_2→p_4→p_1→p_2):各2交換。

長さℓの閉路に対応する位置k_1,…,k_ℓの現在値をv_1,…,v_ℓ、目標値をv_2,…,v_ℓ,v_1とすれば、(k_1,k_2),(k_2,k_3),…,(k_{ℓ−1},k_ℓ)のℓ−1交換で全位置が正しくなる。各閉路の必要な辺重みが残っているので、上の順でa,b,c組を処理できる。a,b,cが0の閉路は飛ばせばよく、三角形だけや4-cycleだけの退化形も含む。

追加交換回数は2a+3b+2cである。一方、順序(p_1,p_2,p_3,p_4)のFはa+b+c+(b+c)+(a+b)=2a+3b+2c。このpの下界を達成したため、残graphでmax_p Fも同値になる。相殺前の全Fはdだけ大きかったので、元の最適回数はd+2a+3b+2c=max_p F(p)。均衡だけから任意の値種類でこの式を結論することはできない。

実装上の注意

  • Cの向きは現在値→目標値。Fでは順列内の順位a<bを用い、対角を除く。
  • O(N)でBを作るには値1..4の頻度を数え、累積頻度で目標区間を定める。比較sortでBを作るなら時間はO(N log N)となる。
  • 閉路の交換列と重み0の補完は証明用。回答の実装では元のCから24順列の最大値を直接取る。
  • 全位置が正しい場合は全F=0。2-cycleだけ、3-cycleだけ、4-cycleだけ、複数閉路が辺を共有する場合を確認する。

復習の核

  • 一操作の変化量から作ったpotentialは下界であり、達成する構成まで示して最適値にする。
  • 頻度圧縮の後も、重みの均衡と小さい頂点数を別々に使う。閉路分解の存在だけでは特定potentialの達成を保証しない。
  • 0の重みを含む退化形まで覆うと、分類証明と実際の入力がつながる。

計算量と制約

時間

O(N+4!·4²)、目標の頻度区分はO(N)で作れる。

空間

O(N)、または誤配置4×4と入力。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2\times 10^5; 1\leq A_i \leq 4; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sort from 1 to 4 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 同値な状態を正規化する

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

    主タグ: 状態・配置の正規化

    補助タグ: 有界全列挙・有限case分解

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

    学習の位置

    体系上の位置: 同値な状態を正規化する

    • 対称操作で同値な状態の標準形と不変量を選べる。

    先に読む単元:

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

    • 交換論による貪欲順の証明。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題