kmjp's blog

競技プログラミング参加記です

CSAcademy Round #50 : D. Min Races

B問題の謎ミスで大幅に時間を溶かした。
https://csacademy.com/contest/round-50/task/min-races/

問題

何人かでレースを行うとその順位は毎回一意であり、人同士の相対的な順位は同じである。
各人にはクラスが設定されている。
レース参加者は、自分より前にいる人が自分より上位のクラスだけの場合勝者となる。

レースの参加者を毎回任意に選べる場合、各人が最低1回優勝するには何回レースを行う必要があるか。

解法

自分より前にゴールする人のうち、自分より下位のクラスの人がいる場合、その人がいない回次でなければ勝者になれない。
言い換えればそのような人のうち最も最後のレースで勝者になった人に対し、その次の回で勝者となれる。

よってRMQを処理できるSegTreeを使いそのような人を順次求めていけばよい。

int N,K;
int C[101010];
int num[101010];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x>>y;
		C[y-1]=x;
	}
	
	int ma=0;
	FOR(i,N) {
		num[i]=1+st.getval(C[i],K+1);
		ma=max(ma,num[i]);
		st.update(C[i],num[i]);
	}
	cout<<ma<<endl;
	
	
}

まとめ

ややこしい設定の割に問題文が短く済んでる。