SRM 580 div2
1015 -> 1115 (+100)
DIV1にあと2回ぐらいでなりたい
easy
すべてのうさぎの組み合わせに対して、時間が重なっているかどうかをみるだけ
#include <cstdio> #include <vector> #include <string> #include <algorithm> using namespace std; class ShoutterDiv2{ public: int count(vector <int> s, vector <int> t){ int a = 0; for(int i = 0; i < s.size(); i++){ for(int j = i+1; j < s.size(); j++){ if(!( t[i] < s[j] || t[j] < s[i] )){ a++; } } } return a; } };
med
うなぎが同じ速さで流れてくるので、うなぎの位置を固定してうさぎがどこの位置でとるか、という風に言い換えることができる。
うなぎの胴体はt[i] から t[i] + l[i] に存在する。
すべての場所についてうなぎが何匹いるか見ればよいが、調べる数が多すぎる。
そこで、うなぎの数が変化するのは頭または尻尾の先端がある場所のみだから、その位置だけを調べればよい。
計算量はO(N^3)
#include <cstdio> #include <vector> #include <string> #include <algorithm> using namespace std; class EelAndRabbit{ public: vector<int> ts; void add(int a){ bool f = true; for(int j = 0; j < ts.size(); j++){ if(ts[j] == a){ f = false; break; } } if(f) ts.push_back(a); } int getmax(vector <int> l, vector <int> t){ int ans = 0; for(int i = 0; i < t.size(); i++){ add(t[i]); add(t[i] + l[i]); } for(int i = 0; i < ts.size(); i++){ for(int j = 0; j < ts.size(); j++){ if(i == j) continue; int a = ts[i], b = ts[j]; bool eel[50]; fill(eel, eel + 50, false); for(int p = 0; p < l.size(); p++){ if(t[p] <= a && a <= t[p] + l[p] || t[p] <= b && b <= t[p] + l[p] ) eel[p] = true; } int c = 0; for(int k = 0; k < 50; k++){ if(eel[k]) c++; } ans = max(ans, c); } } return ans; } };