TopCoder SRM 580 Div1 Medium ShoutterDiv1

本番解けなかったMedium問題を復讐。
http://community.topcoder.com/stat?c=problem_statement&pm=12576

問題

N人(<=2500)の人がいて、それぞれS[i]～T[i]の時間教室にいる。
一瞬でも同じ時間教室にいた人っは友人である。

初期状態では、各人の自己紹介を友人が知っている。
ここで、各友人は自分が知ってる他人の1人分の自己紹介をrepostすることができる。
1回repostすると、その友人の友人にその1人分自己紹介を伝えることができる。
全員が全員分の自己紹介を知るために必要な最小のrepost数を答えよ。

解法

各人がrepost1回で伝えるのは1人分の自己紹介なので、それぞれの人の自己紹介は互いに関係ない。
よって、個々の人の自己紹介が全員に伝わるまでのrepost数の和をとればよい。

i番目の人はS[i]～T[i]の間教室にいるので、より前に教室にいる人と、より後に教室にいる人に徐々にrepostして自己紹介を伝えていけばよい。
ただこれ、両方向にrepostで伝える、と考えるとなかなかうまく解けなかった。

そこでEditorialを見て解答。
まずS[i]が昇順となるようにソートしておく。

i番目の人の自己紹介を全員に通知するには、T[j]が一番早い人から初めて、「1回repostすると、すでに自己紹介を知っている人のうち一番遅いT[j]に対し、S[k]がT[j]より早い人には自己紹介が到達する」と考えて全員に到達するまでのrepost数を数える。
本当はi番目の人から順に1番目に向けてrepostするけど、ここでは逆に1番目からi番目に到達するまでは逆順で必要回数を求める。

ここで、気が付くのは、上記手順にiが登場しないこと。
しかし、ここでT[j]がS[i]より大きい場合、S[i]へのrepostは1手とカウントされない、と考えればよい。
0手の時点でi番目の人(自分)は自己紹介を知ってるわけだしね。

class ShoutterDiv1 {
	public:
	int N;
	vector<pair<int,int> > S;
	string concatvec(vector <string> expr) { return accumulate(expr.begin(),expr.end(),string("")); }
	int count(vector <string> s1000, vector <string> s100, vector <string> s10, vector <string> s1, vector <string> t1000, vector <string> t100, vector <string> t10, vector <string> t1) {
		
		string S1000=concatvec(s1000),S100=concatvec(s100),S10=concatvec(s10),S1=concatvec(s1);
		string T1000=concatvec(t1000),T100=concatvec(t100),T10=concatvec(t10),T1=concatvec(t1);
		S.clear();
		N=S1000.size();
		
		int i,j,mint=9999,ret=0;
		FOR(i,N) {
			S.push_back(make_pair((S1000[i]-'0')*1000+(S100[i]-'0')*100+(S10[i]-'0')*10+(S1[i]-'0'),
				(T1000[i]-'0')*1000+(T100[i]-'0')*100+(T10[i]-'0')*10+(T1[i]-'0')));
			mint = min(mint,S[i].second);
		}
		
		sort(S.begin(),S.end());
			
		FOR(i,N) {
			int cmt = mint;
			int j = 0;
			while(j<N) {
				if(S[i].first <= cmt) cmt=max(cmt,S[i].second);
				int nt=cmt;
				
				while(j<N && S[j].first <= cmt) {
					nt=max(nt,S[j].second);
					j++;
				}
				if(j==N) break;
				if(nt==cmt) return -1;
				cmt=nt;
				ret++;
			}
		}
		return ret;
	}
};

まとめ

本番はi番目の人からどうやって左右に自己紹介を広げていこう、と考えてうまくいかなかった。
それにしてもこの問題、入力形式が珍しいな。