SRM 541 Div2 Medium AntsMeet

問題

2次元座標上の点に,複数の蟻がマップされている.各蟻は進む方向を指定され,その方向にひたすら進み続ける.スピードは全員同じ.蟻同士はぶつかると消滅する.消滅しない蟻の数を答えよ.

解答

時間を1秒ずつすすめ,衝突する蟻の組みを求める.次の時間には残った蟻同士で同様の処理を行う.

蟻は座標軸の点以外でも衝突する場合(すれ違い)があり,その処理に手こずった.
このすれ違いは座標拡大をするとうまく処理できるようだ.
このやり方はうまいので覚えておこう.
SRM 541 250pt : AntsMeet - komiyamの日記

追記: すれ違いだけ別処理にしたが,時刻を0.5刻みにすれば統一的に処理できた.

class AntsMeet
{
public:
  class point{
  public:
    int x;
    int y;
    int dx;
    int dy;
    point(){
      x = y = dx = dy = 0;
    };
    point(int x_, int y_, int dx_, int dy_):x(x_), y(y_), dx(dx_), dy(dy_){};
  };
  int countAnts(vector <int> x, vector <int> y, string direction)
    {
      int max_t = 2010;
      int n = x.size();
      int t, i, j;
      // vector<pair<int, int> > point;
      vector<point> ps(n);
      map<pair<int, int>, int> count;
      for(i = 0; i < n; i++) {
        ps[i].x = x[i];
        ps[i].y = y[i];
        ps[i].dx = ps[i].dy = 0;
        if (direction[i] == 'W') ps[i].dx = -1;
        else if (direction[i] == 'E') ps[i].dx = 1;
        else if (direction[i] == 'N') ps[i].dy = 1;
        else if (direction[i] == 'S') ps[i].dy = -1;
      }
      for(t = 1; t < max_t; t++){
        vector<point> ps2;
        if (ps.empty()) return 0;
        vector<bool> flag(ps.size(), true);
        vector<bool> flag2(ps.size(), true);
        for(i = 0; i < ps.size(); i++){
          for(j = i+1; j < ps.size(); j++){
            if (ps[i].y == ps[j].y
                && abs(ps[i].dx - ps[j].dx) == 2
                && abs(ps[i].x+ps[i].dx*((double)t-0.5) == (ps[j].x+ps[j].dx*((double)t-0.5)))){
              flag[i] = false;
              flag[j] = false;
              cout << "t=" << t << " same y ";
              cout << "(x, y, dx, dy)=(" << ps[i].x << ", " <<  ps[i].y << ", " << ps[i].dx << ", " << ps[i].dy << ") and ("
                   << ps[j].x << ", " <<  ps[j].y << ", " << ps[j].dx << ", " << ps[j].dy << ")" << endl;
            }else if (ps[i].x == ps[j].x
                      && abs(ps[i].dy - ps[j].dy) == 2
                      && abs(ps[i].y+ps[i].dy*((double)t-0.5) == (ps[j].y+ps[j].dy*((double)t-0.5)))){
              flag[i] = false;
              flag[j] = false;
              cout << "t=" << t << " same x ";
              cout << "(x, y, dx, dy)=(" << ps[i].x << ", " <<  ps[i].y << ", " << ps[i].dx << ", " << ps[i].dy << ") and ("
                   << ps[j].x << ", " <<  ps[j].y << ", " << ps[j].dx << ", " << ps[j].dy << ")" << endl;
            }
          }
        }
        for(i = 0; i < ps.size(); i++) if (flag[i]){
            // bool flag = true;
            for(j = i+1; j < ps.size(); j++) if (flag[j]){
                if ((ps[i].x+ps[i].dx*t == ps[j].x+ps[j].dx*t) &&
                    (ps[i].y+ps[i].dy*t == ps[j].y+ps[j].dy*t)){
                  flag2[i] = false;
                  flag2[j] = false;
                  cout << "t=" << t << " ";
                  cout << "(x, y, dx, dy)=(" << ps[i].x << ", " <<  ps[i].y << ", " << ps[i].dx << ", " << ps[i].dy << ") and ("
                       << ps[j].x << ", " <<  ps[j].y << ", " << ps[j].dx << ", " << ps[j].dy << ")" << endl;
                }
              }
          }
        for(j = 0; j < ps.size(); j++) if (flag[j] && flag2[j]){
            ps2.push_back(ps[j]);
          }
        ps = ps2;
      }
      return ps.size();
    }
};