ABC 313 Ex — Group Photo

考察

前列順列 a を固定すると、後列位置 i が越えるべき閾値は c_1=a_1、c_{N+1}=a_N、内部は min(a_{i−1},a_i) である。後列 B を並べられる条件は sorted B_i>sorted C_i である。

A を高さ昇順に挿入すると、既に隣接が確定した辺だけを結んだ path fragments の形が残り、閾値 C のうち現在高さ以下の個数は「挿入済み数+連結成分数」だけで決まる。

採用する候補: A を昇順に挿入し、確定隣接辺が作る連結成分数を状態とする O(N²) の挿入 DP を行う。

具体的な fragment の長さや順序を係数へ集約でき、各高さ段で B との Hall 型 sorted 条件も成分数から判定できる。

棄却する候補: 前列の N! 順列を列挙し、閾値列 C を sort して B と比較する。

N=5000 で順列列挙は不可能で、条件が局所隣接 min だけに依存する構造を使えていない。

新しい最大要素を挿入したとき、単独 fragment を作る・既存 fragment の端へ付く・二 fragment をつなぐ、の三類型で成分数の変化と配置数を数えられる。

段 i、成分数 j なら現在までに確定する閾値数 k=i+j。新たに増える C の値が A_{i+1} 以下の区間に対し、対応する sorted B が十分大きいかだけ検査すればよい。

A,B を昇順 sort する。dp[i][j] を小さい A を i 人挿入し path fragment が j 個ある部分構造数とし、新要素の置き方三種を組合せ係数付きで遷移する。k=i+j で現在確定した C の個数を追い、新しく確定する区間に B_t>A_{i+1} が成り立たない遷移を捨てる。dp[N][1] に対応する完成数を答える。

fragmentは左から右への順序も持つ。0-based でソート済み A,B を使い、dp[0][0]=1 とする。i 人、j fragment の状態から次の A_i を挿入すると、以下の三遷移になる。

操作次の fragment 数係数新しく決まる閾値の個数
独立 fragmentj+1j+1(fragment間の隙間)2
一つの端へ接続j2j(左右の端)1
隣接二 fragmentを連結j−1j−1(隣接する対)0

新閾値は全て A_i である。既知の閾値数 k=i+j に対し、新閾値を一つ以上加える場合は B_k>A_i を要求する。B が昇順なので最小の新しい位置一つの検査で足りる。また次の閾値総数 i+1+j'≤N+1 を満たす遷移だけを残す。j=0 では独立 fragment だけ、j=1 では連結の係数は0。答えは dp[N][1]。

二 fragmentの連結係数は j(j−1) ではなく j−1。順序のあるfragment列で隣接する二本だけをつなげるためであり、この状態定義と係数の組を保つ。

典型の発動条件

値順に最大要素を追加する挿入 DP

発動条件: 順列の隣接関係だけが評価に効き、値の大小がすべて異なるとき。

値順に頂点を足し、確定隣接辺が作る path component 数を状態にする。

sorted matching condition

発動条件: 二集合を一対一に対応させ、各組で片方が閾値を超える必要があるとき。

両者の昇順列を比較する条件へ Hall の条件を圧縮する。

問題固有の要素

隣接 min の multiset は、値を小さい順に見たときの挿入済み path fragments 数によって prefix 個数が決まる。

別の問題へ持ち帰る視点: 順列の隣接 min/max を数える問題では、値 sweep 中の連結成分を状態にする挿入 DP を疑う。

正当性

前列を固定すると後列各位置に必要な高さの下限は、端のAと隣接Aのminである。後列を割り当てられる必要十分条件は、この下限列とBをそれぞれsortして対応する全組がstrictに大小条件を満たすことである。Aを小さい順に挿入すると配置済み要素はfragmentとなり、次要素の挿入は新fragment・片端へ付加・二fragment結合の三種類に一意に分類できる。処理済み人数iとfragment数jから確定済み下限数i+jが分かるので、上述のsorted条件をその時点で検査できる。fragment長や順序の選択数を係数で掛ければ前列を一回だけ数え、後列の存在だけを判定する。

実装上の注意

  • 端点 c_1,c_{N+1} も C に入るため閾値数が i+j になる理由を境界込みで確認する。遷移係数は fragment の左右端と隙間を区別して導く。

復習の核

  • まず固定順列から閾値 multiset C を導き、後列条件を sorted 比較へ落とす。その後、値を一つ挿入したとき C の確定数がどう変わるかを図示する。

計算量と制約

時間

O(N²)、挿入済人数×fragment数、三類型の定数遷移。

空間

O(N)、人数方向rollingとsorted A,B。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 5000; 1 \leq A_i,B_i \leq 10^9; A_i \neq A_j\ (1 \leq i < j \leq N); B_i \neq B_j\ (1 \leq i < j \leq N+1); A_i \neq B_j\ (1 \leq i \leq N, 1 \leq j \leq N+1); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Group Photo の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

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

    主タグ: DPの最小十分状態

    補助タグ: 二部matching・Hall・Kőnig 組合せ係数・数え上げ

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

    学習の位置

    体系上の位置: 最小十分状態からDPを設計する

    • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

    先に読む単元:

    • 二部matching・Hall・Kőnig — 二部グラフの彩色と成分構造で得た考え方と実装を再利用し、二部matching・Hall・Kőnigの発動条件・正当化・境界を重複なく学ぶ。
    • 組合せ係数と対称性で数える — 選び方を通常・Gaussian二項係数で整理し、必要ならStirling変換でrank別計数を基底変換する。

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

    • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題