cafelier@SRM

SRM492 250

あとで | 13:49 |

• 配列サイズ1000と思い込んでいてO(N²)で解くために凝ったことをして間違えたあげくチャレンジフェーズでも思い込みを継続して2撃墜ミス…

typedef complex<double> CMP;
double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); }
int ccw(const CMP& a, CMP b, CMP c) {
   b -= a; c -= a;
   if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
   if( outer_prod(b,c) < 0 ) return -1; // clockwise
   if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line
   if( norm(b) < norm(c) )   return -2; // [a--b]--c on line
   return 0; // [a--c--b] on line
}

class TimeTravellingGardener { public:
   int determineUsage(vector <int> distance, vector <int> height) 
   {
      const int N = height.size();

      distance.insert(distance.begin(), 0);
      partial_sum(distance.begin(), distance.end(), distance.begin());

      vector<CMP> p;
      for(int i=0; i<N; ++i)
         p.push_back( CMP(distance[i], height[i]) );

      int best = N-1;
      for(int i=0; i<N; ++i)
         for(int j=i+1; j<N; ++j)
         {
            best = min(best, score(p[i], p[j], p));
            best = min(best, score(p[i].real(), p[j], p));
            best = min(best, score(p[i], p[j].real(), p));
         }
      return best;
   }

   int score(const CMP& a, const CMP& b, const vector<CMP>& p)
   {
      int s = 0;
      for(int i=0; i<p.size(); ++i)
      {
         if( ccw(a, b, p[i]) == -1 ) return INT_MAX;
         if( ccw(a, b, p[i].real()) == +1 ) return INT_MAX;
         if( ccw(a, b, p[i]) == +1 ) ++s;
      }
      return s;
   }
};

• 配列サイズは50です。2カ所固定して残りが全部上にいるか確かめるだけ