BOJ 28101 - 지구평면설

BOJ 28101 - 지구평면설

일단 안되는 조건을 생각해보자.

$\dfrac{h[1][1]}{h[y][1]} \neq \dfrac{h[1][x]}{h[y][x]}$ 면 불가능하다.

이러한 관계를 이용해 $h[y][x]=\dfrac{h[1][x] \cdot h[y][1]}{h[1][1]}$ 임을 알 수 있다.

$a_1,a_2$ 가 정해진다고 하자.

바뀐 후의 $h[1][1]$ 은 $a_1a_2h[1][1]$ 이 된다.

그럼 $h[y][1]$은 $a_2a_{2y-1}h[y][1]=a_1a_2h[1][1]$ 이 되어야 하므로 $a_{2y-1}$가 정해지는 셈이다.

마찬가지로 $h[1][x]$ 에 대해서도 관계식을 세울 수 있다.

결론적으로 $a_{2y-1}=\dfrac{a_1h[1][1]}{h[y][1]}$ , $a_{2x}=\dfrac{a_2h[1][1]}{h[1][x]}$ 이다.

따라서 $a_1, a_2$ 가 정해지면 모든 $a_i$가 정해짐을 알 수 있다.

$a_i$ 의 가지수를 가장 작게 만드는 방법은 최대한 행에서의 연산과 열에서의 연산이 겹치게 만드는 것이다.

따라서 $a_{2y-1}=a_{2x}$ 가 되게 만들어야 하고, 위 식에서 정리해보면

$$ \begin{aligned} \dfrac{a_1h[1][1]}{h[y][1]}&=\dfrac{a_2h[1][1]}{h[1][x]} \\ \dfrac{a_1}{a_2}&=\dfrac{h[y][1]}{h[1][x]} \end{aligned} $$

여야 한다.

즉, $\dfrac{h[y][1]}{h[1][x]}$ 중 가장 많이 나오는 값을 $\dfrac{a_1}{a_2}$ 로 설정해주면 된다.

구현에서 유의할 점은 완전히 동일한 행과 완전히 동일한 열은 unique하게 처리해주고 개수를 세야한다는 점이다.

이는 연산의 횟수에만 영향을 끼칠 뿐이지 $a_i$ 의 수가 줄어드는데는 영향을 미치지 않기 때문이다.

즉, $\dfrac{2}{4}, \dfrac{15}{30}$ $\dfrac{a_1}{a_2}$ 의 후보에 대해서 $\dfrac{1}{2}$ 라는 값으로 두 개를 세주어야 하지만, $\dfrac{2}{4}, \dfrac{2}{4}$ 는 하나로 처리해주어야 한다는 것이다.

이렇게 unique해주지 않았을 때의 반례는 이 문제의 질문게시판에 존재한다.

void solve() {
   int n;
   cin >> n;
   vvi b(n, vi(n));
   fv2(b);
   for (int y = 0; y < n; y++) {
      for (int x = 0; x < n; x++) {
         if (b[y][x] * b[0][0] != b[y][0] * b[0][x]) {
            cout << -1;
            return;
         }
      }
   }

   map<pi, int> cnt;
   int mx = 0;
   pi mx_pair;

   set<pi> vis;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         int r = b[i][0], c = b[0][j];
         if (hass(vis, mp(r, c))) continue;
         vis.insert(mp(r, c));
         int g = gcd(r, c);
         r /= g, c /= g;
         cnt[mp(r, c)]++;
         if (cnt[mp(r, c)] > mx) {
            mx = cnt[mp(r, c)];
            mx_pair = mp(r, c);
         }
      }
   }

   int ans = 1e9;
   for (int it = 0; it < 2; it++) {
      vi a(n * 2);
      set<pi> ret;
      a[0] = mx_pair.fi, a[1] = mx_pair.se;
      ret.insert({a[0], 1});
      ret.insert({a[1], 1});
      for (int i = 2; i < n * 2; i++) {
         if (i % 2 == 0) {
            int up, down;
            up = a[0] * b[0][0];
            down = b[i / 2][0];
            int g = gcd(up, down);
            up /= g, down /= g;
            ret.insert(mp(up, down));
         } else {
            int up, down;
            up = a[1] * b[0][0];
            down = b[0][i / 2];
            int g = gcd(up, down);
            up /= g, down /= g;
            ret.insert(mp(up, down));
         }
      }
      mina(ans, sz(ret));
      swap(mx_pair.fi, mx_pair.se);
   }
   cout << ans;
}