BOJ 28101 - 지구평면설

image.png

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

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

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

a1,a2a_1,a_2 가 정해진다고 하자.

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

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

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

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

따라서 a1,a2a_1, a_2 가 정해지면 모든 aia_i가 정해짐을 알 수 있다.

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

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

a1h[1][1]h[y][1]=a2h[1][1]h[1][x]a1a2=h[y][1]h[1][x] \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}

여야 한다.

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

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

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

즉, 24,1530\dfrac{2}{4}, \dfrac{15}{30} a1a2\dfrac{a_1}{a_2} 의 후보에 대해서 12\dfrac{1}{2} 라는 값으로 두 개를 세주어야 하지만, 24,24\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;
}

Tags:

Categories:

Updated:

Comments

You may also enjoy