問題
①複数のうなぎが川を流れている。②各うなぎは毎秒１の速さで進む。
③各うなぎに対し、最初に到達する時間ｔと、うなぎの長さｌが与えられる。
④うさぎは２回のｔ時刻だけ、うなぎを捕まえることができる。
選んだｔに対し、そのときに流れているうなぎを全て捕まえることができる。
⑤このとき、捕まえることのできるうなぎの最大数を求める。
解き方
最初に全探索で考える。
各時刻に対しとらえることのできるうなぎの数を洗い出し、
全ての時刻から２つ時刻を選ぶ方法を全通り試して、最大のうなぎの数を返す。
しかし今回はうなぎの長さが１０＾９となるため、
全ての時刻の全探索で解くことができない。
では、選ぶ時刻の数を少なくすることはできないか？と考える。
もう少し考えると、うなぎの数が変化するのは頭と尾のときのみということがわかれば、
高々５０＊２＝１００通りの時刻を調べればよいことがわかる。
全体の計算量はＯ（１００＊５０＝５０００）なのでこの考え方で解くことができる。
コード
class EelAndRabbit {
public: int getmax(vector<int> l, vector<int> t) {
int ans=0;
vector<int> v;
v.clear();
FORE(i,0,t.size()){
v.push_back(t[i]);
v.push_back(t[i]+l[i]);
}
FORE(i,0,v.size()){
FORE(j,i+1,v.size()){
int cur=0;
FORE(k,0,t.size()){
if( (t[k]<=t[i] && t[i]<=t[k]+l[k]) || (t[k]<=t[j] && t[j]<=t[k]+l[k]))cur++;
}
ans=max(ans,cur);
}
}
return ans;
}
};
public: int getmax(vector<int> l, vector<int> t) {
int ans=0;
vector<int> v;
v.clear();
FORE(i,0,t.size()){
v.push_back(t[i]);
v.push_back(t[i]+l[i]);
}
FORE(i,0,v.size()){
FORE(j,i+1,v.size()){
int cur=0;
FORE(k,0,t.size()){
if( (t[k]<=t[i] && t[i]<=t[k]+l[k]) || (t[k]<=t[j] && t[j]<=t[k]+l[k]))cur++;
}
ans=max(ans,cur);
}
}
return ans;
}
};