AtCoder ARC #032 : C - 仕事計画

しょうもないWA。
http://arc032.contest.atcoder.jp/tasks/arc032_3

問題

N個の仕事がある。
各仕事は時刻A[i]～B[i]の間に従事する必要がある。
最大でいくつの仕事に従事するか答えよ。

また、最大数従事できる仕事の組み合わせのうち、辞書順最小のものを求めよ。

解法

想定解法とはちょっと違う解法。

各仕事について、SegTreeを使って「この仕事以降で最大いくつ仕事ができるか」を求める。
そのためには、仕事をA[i]降順にソートし、SegTreeを使ってB[i]～+∞の範囲内を開始時刻とする他の仕事の(仕事数最大値+1)を求めればよい。

後は辞書順最小を求める。
以降の最大仕事数がxとなる仕事の集合をV(x)とする。
まず最初はV(x)のうち最小の仕事番号をyとする。
次に、V(x-1)のうち、y以降に開始できる最小の仕事番号を求め、新たなyとする。
以下同様にV(x-2)、V(x-3)…と順にy以降に開始する最小の仕事番号を求めていけば良い。

なお、AtCoderは行末に余計な空白があるとWAになるようだ。
配列の内容を出力する場合は注意。

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) {
		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;
int nm[1002000];

int N;
ll A[102000],B[102000];
int num[102000];
vector<pair<int,int> > ev;
vector<int> V[101000];
vector<int> R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		A[i]++,B[i]++;
		ev.push_back(make_pair(-A[i],i));
	}
	sort(ev.begin(),ev.end());
	FOR(j,ev.size()) {
		x=ev[j].second;
		num[x]=1+st.getval(B[x],1001005);
		if(num[x]>nm[A[x]]) {
			nm[A[x]]=num[x];
			st.update(A[x],nm[A[x]]);
		}
	}
	
	FOR(i,N) V[num[i]].push_back(i);
	x=-1;
	for(i=100000;i>=0;i--) if(V[i].size()) {
		if(x==-1) {
			x=V[i][0];
		}
		else {
			FOR(y,V[i].size()) {
				if(B[x]<=A[V[i][y]]) {
					x=V[i][y];
					break;
				}
			}
		}
		R.push_back(x);
	}
	
	_P("%d\n",R.size());
	FOR(i,R.size()) {
		if(i) _P(" ");
		_P("%d",R[i]+1);
	}
	_P("\n");
}

まとめ

手を抜いて空白を行末に入れてWA…。