SRM580 Div1 Easy - EelAndRabbit

appletは相変わらず滅多に繋がらない上に最近たまにstatisticsの問題ページが消える
f:id:creep040:20181104183622p:plain

問題

川をn匹のうなぎが泳いでおり、i匹目の長さはa[i]で、時刻t[i]にうなぎの頭がx軸にぶつかる
ある時刻に川に飛び込むと、その瞬間にx軸と交点を持つうなぎを全て捕まえることができる
2回まで川に飛び込めるとき最大で何匹のうなぎを捕まえられるか

1 <= n <= 50
1 <= a[i] <= 10^9
0 <= t[i] <= 10^9

解法

i匹目のうなぎがx軸と交点を持つような時間帯の左端をL[i]、右端をr[i]とする
うなぎの部分集合Sを考えると、(Sの全てのうなぎを1回で捕まえることができる時間帯) = (各うなぎの[L[i], r[i]]の共通範囲) であり、そのような時間帯の左端と右端はSに含まれるあるうなぎの左端と右端に一致する
ということは川に飛び込む時刻の候補は各L[i]とr[i]のみ考えれば十分
たかだか100個しかないから2点の選び方を全部試せばいい

class EelAndRabbit {
public:
	int getmax(vector<int> a, vector<int> t) {
		int n = a.size();
		vector<int> l, r, s;
		rep(i,n) {
			l.push_back(t[i]), r.push_back(t[i]+a[i]);
			s.push_back(t[i]), s.push_back(t[i]+a[i]);
		}
		int res = 0;
		each(i,s) each(j,s) {
			int p = 0;
			rep(k,n) if ((l[k]<=i && i<=r[k]) || (l[k]<=j && j<=r[k])) p++;
			chmax(res,p);
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12575&rd=15500