AOJ 1069 - Squid Multiplication -

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1069&lang=jp

解法

解法1 二分探索

を二分探索で求める。それだけ。

ソースコード

int n, N;
vector<int> even_b, odd_b;

bool check(double x) {
  vector<double> a(2);
  Rep(i, 2) a[i] = (double)even_b[i] / x;
  if ( a[0]*a[1] > (double)odd_b[0] ) return false;  
  else return true;
}

signed main() {  
  while ( cin >> n, n ) {
    N = n * (n+1) / 2;
    even_b.clear();
    odd_b.clear();
    
    Rep(i, N) {
      int b;
      cin >> b;
      if ( b % 2 ) odd_b.pb(b);
      else even_b.pb(b);
    }

    sort(All(even_b));
    sort(All(odd_b));
    
    double l = 1.0, r = (1 << 31)-1;
    int cnt = 100;
    while ( cnt-- ) {
      double mid = (r + l) / 2.0;      
      if ( check(mid) ) r = mid;
      else l = mid;
    }
    
    int ans = (double)r;
        
    cout << ans << endl;
    Rep(i, n) {
      if ( i ) cout << " ";
      cout << even_b[i] / ans;
    }
    cout << endl;
  }

  return 0;
}

解法2 式をたてて計算する

数列eをbに含まれる偶数列(昇順)、数列oをbに含まれる奇数列(昇順)とすると、

参考 http://rhodon.u-aizu.ac.jp:8080/arena/submission_log.jsp?no=3810&runID=2645024

反省とか

あまり考えずに二分探索を書いたのはよくなかった。（しかもコンテスト中はばバグらせた）
数式を変形して簡単な解法がないか考えることも必要そう。