CSAcademy Round #50 (Div. 2 only) Min Races
問題概要
N人から何人か選んで複数回レースをする. N人はKクラスに分かれている.
また,N人の実力は決まっており,レースをするとその実力通りの順位になる.
レースをした時,自分より順位が上の人全員が自分より上のクラスであるならその人は勝利となる.
全員が勝利するためには最低何回レースを行う必要があるか.
クラスはa_i, 実力はb_iで与えられる(どちらも小さい方が高い)
解法
a_iでソートして前から順に見ていく. 毎回各レースの最下位の人の順位を保存しておく.
(少し簡単な問題として自分より順位が上の人が自分以上(ここが違う)のクラスの人であれば勝利とする問題を考える)
ここで,もし最下位の人が自分より順位が上のレースがあるなら,そのようなレースのうち最下位の人が最も順位が低いレースに参加して自分が最下位となれば良い.
また,そのようなレースがないなら自分一人のレースを作れば良い.
最下位の人の順位を保存しておくデータ構造を考えると,二分探索,データの追加,更新ができれば良さそうなので,これはsetで実現できる.
次に,最初の自分と同じクラスが自分以上の順位でも良いという制約を除去して考えると,
同じクラスの場合は下の順位から見て行けば,上の順位を見たときに同じクラスでは自分より順位が下の人しかレースに参加していないため,
そのようなレースに参加することは避けられそうということがわかる(自分より上の人が最下位であるレースにしか参加しないため)
よってa_iの昇順に,a_iが等しい場合はb_iの降順に並べれば良い.( b_i*=(-1)してpairでsortすれば良い )
計算量はO(NlogN)となる.
また想定解としてはb_iでソートすればa_iから最長部分増加列(LIS)を取り除く作業をすればよく,これは最長部分非増加列の長さと一致する.
よくあるDPでも良いしSegmentTreeでも良い.
メモ
想定解の解法知らなかった. そうなりそうなのはわかるが証明できない..
*追記
まさにこれ
数列の要素を頂点と考えてa_iからi<j, a_i<a_jなるa_jに対して辺を貼るとこのグラフはDAGで求める答え(LISを何回取り除けるか)は最小パス被覆に一致する.
またこのDAGは推移閉包なので,Dilworthの定理よりどの二点間にもパスが存在しないような頂点の集合の大きさと一致する.
これは最長部分非増加列の長さそのもの.
推移閉包参考
競プロslackで聞いてよかった.. tozanさんありがとうございました.
