読者です 読者をやめる 読者になる 読者になる

SRM 594 Div2 Medium AstronomicalRecordsEasy

問題

SRM 594 - TopCoder Wiki

太陽系のいくつかの惑星をピックアップしてその距離を示す配列がA, Bの2つある. A, Bの中には同じ同一の惑星を示しているかもしれないが,距離は比率で表しているため容易にはわからない. 考えられる可能性の内この太陽系の惑星の数の最小の数を求める問題.

解答

ポイント

  • 答えはA.size() + B.size()以下になるはず.
  • 比率なのでAの最後の要素と,Bの最初の共通と考えれば,答えはA.size() + B.size()-1以下になるはず.
  • ここでAとBで1つペアを作ってしまえば,A, Bのすべての要素について互いの要素同士の比率が求めることが出来る.

アルゴリズム

AとBの全てのペアを考え,それに合わせAとBのすべての要素の比率を正規化.その異なり数を求め,最小値を返す.

class AstronomicalRecordsEasy
{
public:
  int minimalPlanets(vector <int> A, vector <int> B)
    {
      int n = A.size();
      int m = B.size();
      int i, j;
      int ii, jj;
      int res = n + m;
      for(i = 0; i < n; i++){
        for(j = 0;j < m; j++){
          set<int> planets;
          for(ii = 0; ii < n; ii++){
            planets.insert(A[ii] * B[j]);
          }
          for(jj = 0; jj < m; jj++){
            planets.insert(A[i] * B[jj]);
          }
          res = std::min(res, (int)planets.size());
        }
      }
      return res;
    }
};