SRM 580 Div2 Medium EelAndRabbit

問題

SRM 580 - TopCoder Wiki

うさぎがうなぎを取ろうとしている. 各うなぎはうさぎの方向に同じ速度で動いている. 各うなぎの頭の到達時刻と,うなぎのながさがわかっている. ある時刻でうさぎの目の前にいるうなぎ(頭からしっぽまでのいずれかが目の前にある)は取ることが出来る. うさぎが取ることが出来る,うなぎの最大の数を答える問題.

解答

  • 到達時刻と,うなぎの長さの入力が1,000,000,000なので,単純に時刻を変えてシミュレーションするのはまずそうである.
  • よく考えると,最大のうなぎを取る最善の戦略は,取るタイミングが,あるうなぎの頭が到達した時点,もしくはしっぽが到達した時点ということが分かる*1
  • うなぎの入力は高々50なので,最大50 * 50の時刻についてシミュレーションを行い,最適解を求めれば良い.
using namespace std;


class EelAndRabbit
{
public:
  int getmax(vector <int> l, vector <int> t)
    {
      int i, j;
      int i2, j2;
      int n = l.size();
      set<int> S;
      for(i = 0; i < n; i++){
        S.insert(t[i]);
        S.insert(t[i]+l[i]);
      }
      int k;
      vector<int> ts(S.begin(), S.end());
      int m = ts.size();
      int res = 0;
      for(i = 0; i < m; i++){
        for(j = i+1; j<m; j++){
          vector<bool> chatched(n, false);
          int v = 0;
          for(k = 0; k < n;k++){
            if ((t[k] <= ts[i] && ts[i] <= t[k]+l[k]) ||
                (t[k] <= ts[j] && ts[j] <= t[k]+l[k]))v++;
          }
          res = max(res, v);
        }
      }
      return res;
    }
};

*1:もっとよく考えると頭の到達時刻だけでよい