ABC 217 F — Make Pair

考察

二人が選ばれる時点では隣接しているため、最初の並びに弧を描くと最終的なペアは交差しない。特に区間の左端の生徒が位置 2k の生徒と組むなら、その二人の間にいる 2k-2 人は先に区間内だけで消えていなければならない。サンプル2では同じ二組を作っても取り除く順番が違えば別解として数えるため、非交差なペア分割の個数だけでなく、独立な区間の操作列を混ぜる順番も数える必要がある。左端と位置 2k の生徒が仲良しなら、内側 k-1 組の処理後にその二人を消す k 操作と、右側 j-k 操作を二項係数 C(j,k) 通りに interleave できる。

採用する候補: 偶数長区間を全員取り除く方法数とし、左端の相手で分割する区間 DP に、左右の操作を混ぜる二項係数を掛ける。

左端の相手を固定すると内側と右側が独立な偶数長区間になり、仲の良さ、ペア構造、操作順の三要素を過不足なく積に分解できる。

棄却する候補: 各時点で隣接する仲の良い組を列挙し、削除列を再帰的に全探索する。

同じ残存区間構造へ至る多数の順番を個別に探索するため指数的に分岐し、2N=400 では扱えない。

dp[i][j] を生徒 i+1 から i+2j を全て消す方法数とし、左端の相手 i+2k を全て試す。仲良しの場合に dp[i+1][k-1]、dp[i+2k][j-k]、C(j,k) を掛けて加算し、空区間を 1 とする。

典型の発動条件

端点固定の区間 DP

発動条件: 隣接要素の削除によって元の列の区間が独立に閉じ、最終的な対応が非交差になるとき。

左端の相手を固定して内側と残りの右区間へ分割し、短い偶数長区間から計算する。

独立な操作列の interleave

発動条件: 独立な二部分の完成方法に加え、両部分の操作を行う時系列も区別して数えるとき。

一方から k 回、他方から j-k 回を選ぶ位置を二項係数 C(j,k) で数える。

問題固有の要素

外側の一組は内側を全て消した後で初めて隣接するため、その組自身の削除を内側ブロックの最後の一操作として数える。

別の問題へ持ち帰る視点: 削除過程を数える問題では、完成した組合せだけでなく各依存関係が作る操作順の自由度を別因子として確認する。

正当性

左端の相手を固定すると二人を隣接させるため内側を先に全除去する必要がある。内側完了+当該pairのk操作と右側N−k操作は互いに独立で相対順を保つshuffleがC(N,k)通り。相手選択で分類は排他的、区間帰納法で全除去列を数える。

実装上の注意

  • 区間長は人数ではなく組数 j で管理し、左端の相手は偶奇から i+2k だけを試す。全 i について dp[i][0]=1 とし、添字と法 998244353 の積を崩さない。

復習の核

  • N=2 で離れた二組が独立に消える例を作り、二項係数を掛けない数え方が操作順を落とすことを確認する。

計算量と制約

時間

生徒2N人、友好辺M。区間と左端相手列挙で O(N³)、二項係数前計算O(N²)。

空間

区間DPと二項係数 O(N²)、友好表 O(N²)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 200; 0 \leq M \leq N(2N-1); 1 \leq A_i < B_i \leq 2N; All pairs (A_i, B_i) are distinct.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Make Pair の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間合成・領域分割DP

主題
  • 区間合成・領域分割DP: 区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 区間合成・領域分割DP

    補助タグ: 組合せ係数・数え上げ

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

    学習の位置

    体系上の位置: 区間合成・領域分割DP

    • 区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題