[AtCoder] diverta 2019 Programming Contest 2 B – Picking Up

問題

方針

\( p, q \) を固定して全探索を行う

ボールの各座標を位置ベクトルとして、 \( \vec{v}_i = (x_i, y_i) \) と表すことにします。\( p, q \) の候補は、任意の二つの位置ベクトルの差分として、\( \vec{u}_{i, j} = (x_i – x_j, y_i – y_j) \) とします。これは、\( N \) 個から \( 2 \) 個選ぶ組み合わせに、向きを考慮して、\( N(N – 1) \) 通りあることになります。 なぜこのような候補になるかというと、これ以外の \( p, q\) の値は、コストが \( 0 \) になる可能性がないからです。

また、コストが掛からないときは、どういうことかというと、

\[ \vec{v}_i =\vec{v}_j + \vec{u}_{k, l} \ (i \neq j \wedge k \neq l)\]

を満たすということです。したがって、\(\vec{u}_{k, l} \) と \( \vec{v}_i, \vec{v}_j \) の全探索行うので、\( 4 \) 重ループの計算を行えば良いです。ここで、注意する点は同じ座標のボールは存在しないことから、\( \vec{u}_{k, l} \) と \( \vec{u}_j \) を固定したとき、上記の式を満たす \( \vec{v}_i \) は最大でも一つしかありません。

コード

提出したコード

全探索

  int ans = N;
  for (int i = 0; i < N - 1; i++) {
    for (int j = 0; j < N; j++) {
      if (i == j) continue;
      int p = x[i] - x[j];
      int q = y[i] - y[j];
      int cnt = 0;
      for (int k = 0; k < N; k++) {
        for (int l = 0; l < N; l++) {
          if (k == l) continue;
          if (x[k] - x[l] == p && y[k] - y[l] == q) {
            cnt++;
          }
        } 
      }
      ans = min(ans, N - cnt);
    }
  }