SRM580 Div1 Easy - EelAndRabbit
appletは相変わらず滅多に繋がらない上に最近たまにstatisticsの問題ページが消える
問題
川を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