TopCoder SRM 580 Div1 Easy EelAndRabbit

さてSRM580。Medium600ptに嫌な予感。
Mediumは頑張ったけど微妙に数字が合わずアウト。
Easyしか解けなかったわけだが、幸い１つChallengeに成功して250ptを超えたためそこそこの順位になってレート回復。
http://community.topcoder.com/stat?c=problem_statement&pm=12575

問題

N匹のウナギが川を下ってくる。ウナギは速度１で川を下ってきており、ウナギの頭が川の座標０を通過する時刻T[i]と、胴体の長さL[i]が与えられる。
途中、川のある位置で２回までその時点にいるウナギをすべて捕まえることができる。
捕まえられる最大のウナギの数を答えよ。

解法

長さや時間は最大10^9なので、全部の時間を試すとTLEになる。
しかし、実際には試す必要がある時間は、全ウナギに対し座標0に到達する時間T[i]と座標0から胴体が抜ける時間T[i]+L[i]だけ。
よって2N通りの時間で試せばよい。

2N通りの時間について、捕まえられるウナギをbitmapで覚えておき、最後に2Nから２つ選んでbitmapのorを取ったbitcountの最大値が答え。

以下のコードではわざわざ座標圧縮してしまった。
おかげでコーディングに無駄な時間がかかった。
まぁChallengeのおかげで250pt越えたからよかったけど、それが無いと数十秒の違いで大きく順位に差がつくポイント帯に入っていて危なかったね。

inline ll bitcount(ll n) { return __builtin_popcountll(n);}

class EelAndRabbit {
	map<int,int> S;
	int N;
	ll mask[101];
	public:
	int getmax(vector <int> l, vector <int> t) {
		int i,j;
		S.clear();
		N=l.size();
		FOR(i,N) {
			l[i]+=t[i];
			S[l[i]]=1;
			S[t[i]]=1;
		}
		
		i=0;
		for(map<int,int>::iterator mit=S.begin();mit!=S.end();mit++) mit->second=i++;
		
		FOR(i,N) {
			l[i]=S[l[i]];
			t[i]=S[t[i]];
		}
		
		ZERO(mask);
		FOR(i,101) {
			FOR(j,N) {
				if(i>=t[j] && i<=l[j]) mask[i] |= 1LL<<j;
			}
		}
		
		int ma=0;
		FOR(i,101) {
			FOR(j,101) {
				ma=max(ma,(int)bitcount(mask[i]|mask[j]));
			}
		}
		return ma;
	}
};

まとめ

座標圧縮を思いついてこれで行けると思ったら、単に2N通りの時刻を調べればそれで十分だった…。
あいにく青コーダーの多い部屋だったけど、10^9通りループを回している人はいなかったな。