CSAcademy Min Races - kou6839の日記

csacademy.com

＜問題＞
$N$ 人でレースを行います。
$N$ 人それぞれクラス $A_i$ と全員でレースした際の順位 $B_i$ ( $0 \leq i \leq N-1$ )が与えられます。
何回かレースを行って、 $N$ 人すべてが最低１回ずつ勝利するようにします。
各レースでは $N$ 人の中から、出場選手を自由に選ぶことができます。
各レースで、自分より早い人のクラスが、自分のクラスよりも小さければ勝利となります。
( つまり、勝利する選手を $i$ とすると、全ての $B_j \lt B_i$ となる $j$ について、 $A_j \lt A_i$ 　となってればよい )
レース回数を最小にするとき、いくらになるか。

＜解説＞
Aさんが勝利する際は、条件より、自分より早い人のクラスが自分よりちいさければいいです。
また、１度のレースで勝者をできるだけ多くだすためには、(クラス・順位)のペアを昇順にできるだけ多く並べればよいです。

そのためには、順位でソートしたあとに、クラスが狭義単調増加になるように、部分列を最小限に作ればよいです。
これまで作った部分列の最大の値を持っておいて、
①それらよりも小さい場合は、新しい部分列を作る
②そうでない場合は、できるだけ大きいものの後ろにつける
という操作を、部分列の最後の値（最後尾）だけを持って計算します。
部分列の数が答えになります。
(以下のコードで、dequeでなくvectorでやると、①の操作が遅いためTLEしました）

＜コード＞

int main() {

	int n, m;
	cin >> n >> m;
	vector<pii> v;

	rep(i, n) {
		int a, b;
		cin >> a >> b;
		v.pb({ b,a });
	}
	SORT(v);

	deque<int> l;
	rep(i, n) {
		if (i == 0) {
			l.pb(v[i].second);
			continue;
		}
		auto index = lower_bound(ALL(l), v[i].second);
		if (index == l.begin()) {
			l.push_front(v[i].second);
		}
		else {
			l[index-l.begin() - 1] = v[i].second;
		}
	}
	P(l.size());
	return 0;
}

＜感想＞
問題文と解説が難しかった・・・