kmjp's blog

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

Codeforces ECR #030 : E. Awards For Contestants

相変わらず詰めが甘い…。
http://codeforces.com/contest/873/problem/E

問題

N人の参加者がいたコンテストで、各人の解いた問題数はA[i]とする。
参加者の一部の人に、1~3の3種類の賞状を与える。
この時以下の条件を守るように与えたい。

  • 1人は1つだけ賞状を受け取ることができる。受け取らなくてもよい。
  • ある賞状をもらう人数は、他の症状をもらう人数の倍以下でなければならない。
  • 各賞状は最低1名以上に与える。
  • 下位の賞状をもらった人より上位の賞状をもらった人の方が問題数が少ない、という与え方は不可。

上記条件のうち、さらに下記を満たす与え方を答えよ。

  • 1番の賞状をもらう人の最低解答問題数と、2番の賞状をもらう人の最大解答問題数の差を最大化する
  • 上記条件がタイなら、2番の賞状をもらう人の最低解答問題数と、3番の賞状をもらう人の最大解答問題数の差を最大化する
  • 上記条件がタイなら、3番の賞状をもらう人の最低解答問題数と、賞状をもらわない人の最大解答問題数の差を最大化する

解法

賞状の枚数さえ決まれば、あとは問題数の多い順に配分すればよい。
よって参加者を問題数降順にソートしておき、あとは枚数を決めることを考えよう。

Nはそこまで大きくないので、1,2番の賞状をもらう人数を決めよう。
そうすると3番目のもらえる人の人数の範囲が確定する。
範囲が定まった後は、上記問題数の差の最大値を求めるため、次の順位の人との解答問題数の差に対するRMQを答えられるようにしておけばよい。

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	static V const def=0;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return max(l,r);}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(def,i);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(0,0);
		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]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_Pair<int,1<<13> st;


int N;
vector<pair<int,int>> V;
int ret[5050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	V.push_back({0,-1});
	FOR(i,N) cin>>x, V.push_back({x,i});
	sort(ALL(V));
	reverse(ALL(V));
	
	FOR(i,N) {
		st.update(i,V[i].first-V[i+1].first);
	}
	
	int d12=-1,d23=0,d34=0;
	int mx,my,mz;
	for(x=1;x<=N;x++) {
		
		for(y=1;x+y<N;y++) if(x<=2*y && y<=2*x) {
			int zmin=(max(x,y)+1)/2;
			int zmax=min(N-x-y,min(x,y)*2);
			if(zmin>zmax) continue;
			
			
			auto dm=st.getval(x+y+zmin-1,x+y+zmax);
			
			if(V[x-1].first-V[x].first>d12 ||
			   (V[x-1].first-V[x].first==d12 && V[x+y-1].first-V[x+y].first>d23) ||
			   (V[x-1].first-V[x].first==d12 && V[x+y-1].first-V[x+y].first==d23 && dm.first>d34)) {
				d12=V[x-1].first-V[x].first;
				d23=V[x+y-1].first-V[x+y].first;
				d34=dm.first;
				mx=x;
				my=y;
				mz=dm.second-(x+y)+1;
			}
		}
	}
	
	FOR(i,N) {
		if(i<mx) ret[V[i].second]=1;
		else if(i<mx+my) ret[V[i].second]=2;
		else if(i<mx+my+mz) ret[V[i].second]=3;
		else ret[V[i].second]=-1;
	}
	FOR(i,N) _P("%d%c",ret[i],(i==N-1)?'\n':' ');
	
}

まとめ

くだらないミスした。