ABC 238 F — Two Exams

考察

市民を一回目の順位順に並べ、順位 i の人の二回目順位を A_i とすれば、一回目の優劣は処理順に埋め込める。

今の人を選ぶとき問題になるのは、先に選ばなかった人のうち二回目順位が最良の人だけである。

棄却する候補: K 人の全組合せを列挙し、選んだ人より両試験で上位の未選択者がいないか検査する。

組合せ数が指数的で N=300 を扱えず、支配条件の推移性も利用していない。

採用する候補: 一回目順位の昇順に走査し、選択人数 j と、それまでの未選択者の最小二回目順位 k を状態にして選ぶ・選ばないを遷移する。

現在の A_i が k より小さい場合に限り選択可能で、未選択なら k を min(k,A_i) にするだけなので過去を二値の境界へ圧縮できる。

一回目で現在より上位かつ未選択の人 y が存在するとき、現在を選べる条件は全ての Q_y より現在の Q が良いこと、すなわち A_i<min Q_y である。

二次元支配順序の下向き閉包を数える問題を、一方の座標で sweep し、未選択集合が課す他方座標の最小境界だけを持つ DP にする。

典型の発動条件

一方の順位で整列する支配関係 DP

発動条件: 二つの全順序でともに優る要素との選択整合性が課され、片方の順位が重複しないとき。

一方の順位順に決定してその座標を状態から消し、もう一方の順位境界だけを残す。

未選択集合の最小値による状態圧縮

発動条件: 将来の選択可否が過去に除外した要素全てとの大小比較で決まり、最も厳しい境界だけ見ればよいとき。

未選択者の最小二回目順位を持ち、選択時は境界比較、非選択時は min 更新を行う。

問題固有の要素

P と Q を市民番号のまま扱わず A[P_i]=Q_i と置くと、一回目順位 i の人を順に処理できる。

別の問題へ持ち帰る視点: 複数の順列順位が与えられたら、一方の逆順列で要素を並べ直して座標対の列に正規化する。

正当性

第一順位順に処理すると現在より第一試験で上位の者は全て処理済み。現在を選ぶとき両試験で優れた未選択者がいない条件は、現在の第二順位が未選択者全体の最小第二順位より小さいことと同値。したがって未選択集合の履歴はその最小値だけで十分。選択人数とその境界を状態にし、選ぶ・選ばないを両方遷移すれば、支配する人を含む必要条件を全て守ったK人集合を一度ずつ数える。

実装上の注意

  • 未選択者がまだいない状態の境界は N+1 とし、初期状態 dp[0][N+1]=1 にする。
  • 選ぶ遷移は A_i<k のときだけ j を一つ増やし、選ばない遷移では j を保って k=min(k,A_i) とする。

復習の核

  • 二次元順序の制約では、片方の座標で sweep した後に過去集合から必要な極値だけを特定する。
  • 選択集合が支配順序に関して閉じる条件は、選ぶ側よりも「過去に選ばなかった最強の要素」が作る禁止境界から考える。

計算量と制約

時間

O(N²K)。

空間

O(NK)。処理人数次元をrollingする。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All values in input are integers.; 1 \le N \le 300; 1 \le K \le N; Each of P and Q is a permutation of (1,2,...,N).

出典

分類・前提・執筆情報

掲載状態: 収録済み

Two Exams の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 列・subsequence DP

主題
  • 列・subsequence DP: 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 列・subsequence DP

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

      学習の位置

      体系上の位置: 列・subsequence DP

      • 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題